Повторний логарифм

В інформатиці, повторний логарифм або ітерований логаритм[1] від n, записується як ${\displaystyle \log ^{*}n}$ (зазвичай читається як "лог зірка"), це необхідна кількість повторних логарифмувань перед тим як результат стає меншим або рівним 1. Найпростіше формальне визначення цієї рекурсивної функції:

${\displaystyle \log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leq 1;\\1+\log ^{*}(\log n)&{\mbox{if }}n>1\end{cases}}}$

На додатних дійсних числах, неперервний суперлогарифм (обернена тетрація) по суті тотожний:

${\displaystyle \log ^{*}n=\lceil {\text{slog}}_{e}(n)\rceil }$

але на від'ємних дійсних числах, ${\displaystyle \log ^{*}}$ є 0, тоді як ${\displaystyle \lceil {\text{slog}}_{e}(-x)\rceil =-1}$ для додатних x, отже, дві функції різняться на від'ємних числах.

Демонстрація lg* 4 = 2

В інформатиці ${\displaystyle \lg ^{*}}$ часто використовують для позначення двійкового повторного логарифма, який повторює двійковий логарифм. Повторний логарифм переводить будь-яке додатне число в ціле. Графічно, це можна уявити як кількість зигзагів потрібних, щоб досягти проміжку ${\displaystyle [0,1]}$ на осі x.

Математично, повторний логарифм однозначно означений не тільки для основ 2 і e, але для будь-якої основи більшої ніж ${\displaystyle e^{1/e}\approx 1.444667}$.

Аналіз алгоритмів

Повторний логарифм стає в пригоді в аналізі алгоритмів і складності обчислень, з'являючись у часових і просторових границях складності таких як:

• Знаходження тріангуляції Делоне множини вершин відомих як евклідове мінімальне кістякове дерево: увипадковлений ${\displaystyle O(n\log ^{*}n)}$ час[2]
• Алгоритм Фюрера для множення цілих: ${\displaystyle O(n\log n2^{\lg ^{*}n})}$
• Знаходження приблизного максимуму (елемент не менше медіани): ${\displaystyle \lg ^{*}n-4}$ до ${\displaystyle \lg ^{*}n+2}$ паралельних операцій[3]

Повторний алгоритм надзвичайно повільно зростає, набагато повільніше ніж сам логарифм. Для значень n значимих для підрахунку швидкодії алгоритмів втілених на практиці (тобто, ${\displaystyle n\leq 2^{65536},}$ що значно більше ніж кількість атомів у відомому всесвіті), повторний логарифм з основою 2 має значення не більше 5.

x	${\displaystyle \lg ^{*}x}$
(−∞, 1]	0
(1, 2]	1
(2, 4]	2
(4, 16]	3
(16, 65536]	4
(65536, 2^65536]	5

Більші основи дають менші логарифми. Насправді, єдина відома функція часто використовувана у теорії складності, що зростає повільніше це обернена функція Акермана.

Примітки

1. Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 3.2: Стандартні позначення та поширені функції. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
2. Olivier Devillers, "Randomization yields simple O(n log* n) algorithms for difficult ω(n) problems.". International Journal of Computational Geometry & Applications 2:01 (1992), pp. 97–111.
3. Noga Alon and Yossi Azar, "Finding an Approximate Maximum". SIAM Journal of Computing 18:2 (1989), pp. 258–267.