Logaritm iterat

În informatică, logaritmul iterat de n ori, scris log* n, 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ță:

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

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

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

de exemplu, în baza b logaritmul iterat este ${\displaystyle \log ^{*}n=y}$ dacă n este în intervalul ${\displaystyle ^{y-1}b<n\leq \ ^{y}b}$, unde ${\displaystyle {^{y}b}=\underbrace {b^{b^{\cdot ^{\cdot ^{b}}}}} _{y}}$ este notația pentru tetrație. Însă pe numerele reale negative log* este 0, întrucât pentru x pozitiv ${\displaystyle \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 e. Valoarea logaritmului iterat poate fi găsită prin „zigzaguri” pe curba ${\displaystyle y=log_{b}(x)}$ de la valoarea inițială n, pe intervalul ${\displaystyle [0,1]}$. În acest caz b = e. Zigzagul pornește de la punctul ${\displaystyle (n,0)}$ și se mută iterativ către ${\displaystyle (n,log_{b}(n))}$, la ${\displaystyle (0,log_{b}(n))}$, la ${\displaystyle (log_{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 ${\displaystyle [0,1]}$ pe axa x.

În informatică lg* este folosit de obicei pentru a indica logaritmul iterat binar, care iterează logaritmul binar (în baza ${\displaystyle 2}$) în loc de logaritmul natural (în baza e).

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

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, 2^65536]	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 O(n log* n).[1]
• 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.[2]
• Algoritmul distribuit Richard Cole și Uzi Vishkin pentru colorarea grafurilor: O(log* n) runde de comunicare sincronă.[3][4]
• Efectuarea unirii rapide ponderate cu compresie de cale.[5]

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^65536, 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ă.

Note

1. en 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.
2. en Noga Alon and Yossi Azar, "Finding an Approximate Maximum". SIAM Journal on Computing 18:2 (1989), pp. 258–267.
3. en Richard Cole, Uzi Vishkin: "Deterministic coin tossing with applications to optimal parallel list ranking", Information and Control 70:1(1986), pp. 32–53.
4. en Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms, I, MIT Press and McGraw-Hill. Section 30.5
5. en Union Find Algorithms, princeton.edu, accesat 2021-06-01

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