În informatică, logaritmul iterat de ori, scris , 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ță:
Pe numerele reale pozitive, superlogaritmul continuu (inversul tetrației) este în esență echivalentul:
de exemplu, în baza b logaritmul iterat este dacă este în intervalul , unde este notația pentru tetrație. Însă pe numerele reale negative log* este , întrucât pentru pozitiv , deci cele două funcții diferă pentru argumentele negative. right|300px|thumb|Demonstrația logaritmului iterat log* 4 = 2 pentru baza . Valoarea logaritmului iterat poate fi găsită prin „zigzaguri” pe curba de la valoarea inițială , pe intervalul . În acest caz = . Zigzagul pornește de la punctul și se mută iterativ către , la , la 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 pe axa .
Î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 ).
Matematic, logaritmul iterat este bine definit pentru orice bază mai mare decât , nu doar pentru bazele și .
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 (n log* n). 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. 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. Noga Alon and Yossi Azar, "Finding an Approximate Maximum". SIAM Journal on Computing 18:2 (1989), pp. 258–267. Algoritmul distribuit Richard Cole și Uzi Vishkin pentru colorarea grafurilor: (log* n) runde de comunicare sincronă. Richard Cole, Uzi Vishkin: "Deterministic coin tossing with applications to optimal parallel list ranking", Information and Control 70:1(1986), pp. 32–53. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms, I, MIT Press and McGraw-Hill. Section 30.5 Efectuarea unirii rapide ponderate cu compresie de cale. Union Find Algorithms, princeton.edu, accesat 2021-06-01
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
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
Categorie:Analiză matematică Categorie:Logaritmi