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ță:
Pe numerele reale pozitive, superlogaritmul continuu (inversul tetrației) este în esență echivalentul:
de exemplu, în baza b logaritmul iterat este dacă n este în intervalul , unde este notația pentru tetrație. Însă pe numerele reale negative log* este 0, întrucât pentru x pozitiv , deci cele două funcții diferă pentru argumentele negative.
![](http://upload.wikimedia.org/wikipedia/commons/c/c3/Iterated_logarithm.png)
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 pe axa x.
În informatică lg* este folosit de obicei pentru a indica logaritmul iterat binar, care iterează logaritmul binar (în baza ) în loc de logaritmul natural (în baza e).
Matematic, logaritmul iterat este bine definit pentru orice bază mai mare decât , nu doar pentru bazele și e.
Analiza algoritmilor
[modificare | modificare sursă]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 O(n log* n).[1]
- Algoritmul Fürer pentru înmulțirea întregilor: O(n log n 2O(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 ≤ 265536, 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