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[modificare | modificare sursă]

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

\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:

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

de exemplu, în baza b logaritmul iterat este $\log ^{*}n=y$ dacă $n$ este în intervalul $^{y-1}b<n\leq \ ^{y}b$ , unde ${^{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 $\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 $y=log_{b}(x)$ de la valoarea inițială $n$ , pe intervalul $[0,1]$ . În acest caz $b$ = $e$ . Zigzagul pornește de la punctul $(n,0)$ și se mută iterativ către $(n,log_{b}(n))$ , la $(0,log_{b}(n))$ , la $(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 $[0,1]$ pe axa $x$ .

Î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 $e$ ).

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 $e$ .

Analiza algoritmilor[modificare | modificare sursă]

Logaritmul iterat în baza 2
x	log* x
(−∞, 1]	0
(1, 2]	1
(2, 4]	2
(4, 16]	3
(16, 65536]	4
(65536, 2⁶⁵⁵³⁶]	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⁶⁵⁵³⁶, 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[modificare | modificare sursă]

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

Bibliografie[modificare | modificare sursă]

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

Portal Matematică

[1] 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] Noga Alon and Yossi Azar, "Finding an Approximate Maximum". SIAM Journal on Computing 18:2 (1989), pp. 258–267.

[3] Richard Cole, Uzi Vishkin: "Deterministic coin tossing with applications to optimal parallel list ranking", Information and Control 70:1(1986), pp. 32–53.

[4] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms, I, MIT Press and McGraw-Hill. Section 30.5

[5] Union Find Algorithms, princeton.edu, accesat 2021-06-01

[1]

[2]

[3]

[4]

[5]