Logaritm iterat

În informatică, logaritmul iterat de Format:Mvar ori, scris Format:Log-star Format:Mvar, este de câte ori trebuie aplicată funcția logaritm iterativ înainte ca rezultatul să fie mai mic sau egal cu 1.

Definiție

Cea mai simplă definiție formală este rezultatul următoarei relații de recurență:

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

Pe numerele reale pozitive, superlogaritmul continuu (inversul tetrației) este în esență echivalentul:

${\log }^{*}n=\lceil {\mathrm{s}\mathrm{l}\mathrm{o}\mathrm{g}}_e(n)\rceil$

de exemplu, în baza b logaritmul iterat este ${\log }^{*}n=y$ dacă Format:Mvar este în intervalul ${y-1}^{}b<n\le {}^{y}b$, unde ${}^{y}b=\underset{y}{\underbrace{b^{b^{{\cdot }^{{\cdot }^b}}}}}$ este notația pentru tetrație. Însă pe numerele reale negative log* este Format:Mvar, întrucât pentru Format:Mvar pozitiv $\lceil {\text{slog}}_e(-x)\rceil =-1$, deci cele două funcții diferă pentru argumentele negative.

Demonstrația logaritmului iterat log* 4 = 2 pentru baza Format:Mvar. Valoarea logaritmului iterat poate fi găsită prin „zigzaguri” pe curba $y=lo{g}_b(x)$ de la valoarea inițială Format:Mvar, pe intervalul $[0,1]$. În acest caz Format:Mvar = Format:Mvar. Zigzagul pornește de la punctul $(n,0)$ și se mută iterativ către $(n,lo{g}_b(n))$, la $(0,lo{g}_b(n))$, la $(lo{g}_b(n),0)$ etc.

Logaritmul iterat acceptă ca argument orice număr real pozitiv, iar rezultatul este un număr întreg. Grafic, poate fi înțeles ca numărul de „zigzaguri” necesare în figura alăturată pentru a atinge intervalul $[0,1]$ pe axa Format:Mvar.

În informatică lg* este folosit de obicei pentru a indica logaritmul iterat binar, care iterează logaritmul binar (în baza $2$) în loc de logaritmul natural (în baza Format:Mvar).

Matematic, logaritmul iterat este bine definit pentru orice bază mai mare decât $e^{1/e}\approx 1.444667$, nu doar pentru bazele $2$ și Format:Mvar. Format:-

Analiza algoritmilor

Logaritmul iterat în baza 2

x	log* x
(−∞, 1]	0
(1, 2]	1
(2, 4]	2
(4, 16]	3
(16, 65536]	4
(65536, 265536]	5

Logaritmul iterat este util în analiza algoritmilor și a complexității calculului, apărând în limitele complexității timpului și spațiului unor algoritmi precum:

• Găsirea triangulării Delaunay a unei mulțimi de puncte cunoscând arborele acoperitor minim euclidian: timp randomizat Format:Mvar(n log* n).
• Algoritmul Fürer pentru înmulțirea întregilor: O(n log n 2^O(log* n)).
• Găsirea unui maxim aproximativ (element cel puțin la fel de mare ca mediana): log* n − 4 la log* n + 2 operații paralele.
• Algoritmul distribuit Richard Cole și Uzi Vishkin pentru colorarea grafurilor: Format:Mvar(log* n) runde de comunicare sincronă.
• Efectuarea unirii rapide ponderate cu compresie de cale.

Logaritmul iterat crește într-un ritm extrem de lent, mult mai lent decât logaritmul în sine. Pentru toate valorile n relevante pentru analiza timpilor de funcționare a algoritmilor implementați în practică (de exemplu n ≤ 2⁶⁵⁵³⁶, care este cu mult mai mare decât numărul estimat de atomi din universul cunoscut), logaritmul iterat în baza 2 are o valoare nu mai mare de 5.

Bazele mai mari dau logaritmi iterați mai mici. Singura funcție utilizată curent în teoria complexității care crește mai lent este funcția Ackermann inversă.

Bibliografie

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms, ed. a II-a, MIT Press and McGraw-Hill, cap. 3.2: Standard notations and common functions, p. 55–56