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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примітки

↑ Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2009) [1990]. 3.2: Стандартні позначення та поширені функції. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
↑ 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.
↑ Noga Alon and Yossi Azar, "Finding an Approximate Maximum". SIAM Journal of Computing 18:2 (1989), pp. 258–267.

[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.

[1]

[2]

[3]

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

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

Примітки

Навігаційне меню

Пошук