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

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

${\log }^{*}n:=\{\begin{array}{cc}0& \text{if }n\le 1;\\ 1+{\log }^{*}(\log n)& \text{if }n>1\end{array}$

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

${\log }^{*}n=\lceil {\text{slog}}_e(n)\rceil$

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

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

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

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

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

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

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

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

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

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