Logaritm iterat
În informatică , logaritmul iterat al unui număr n , notat (citiți „stea jurnal” sau „stea jurnal”), este de câte ori trebuie să i se aplice logaritmul înainte ca rezultatul să fie mai mic sau egal cu 1. funcția este utilizată pentru a descrie complexitatea anumitor algoritmi, în special în algoritmi distribuiți .
Buturuga∗(nu){\ displaystyle \ log ^ {*} (n)}
Definiție
De bază iterată logaritm b poate fi definită prin:
Buturugab∗nu: ={0dacă nu≤1;1+Buturugab∗(Buturugabnu)dacă nu>1.{\ displaystyle \ log _ {b} ^ {*} n: = {\ begin {cases} 0 & {\ mbox {si}} n \ leq 1; \\ 1+ \ log _ {b} ^ {*} (\ log _ {b} n) și {\ mbox {si}} n> 1. \ end {cases}}}Pe numere reale pozitive, super-logaritmul continuu ( în) invers ( tetrarea ) este în esență echivalent:
Buturugae∗nu=⌈sloge(nu)⌉{\ displaystyle \ log _ {e} ^ {*} n = \ lceil \ mathrm {slog} _ {e} (n) \ rceil}Următorul tabel oferă valorile logaritmului iterat (în baza 2):
X{\ displaystyle x}
|
Buturuga2∗X{\ displaystyle \ log _ {2} ^ {*} x}
|
---|
]-∞;1]{\ displaystyle] - \ infty; 1]} |
0
|
]1,2]{\ displaystyle] 1,2]} |
1
|
]2,4]{\ displaystyle] 2,4]} |
2
|
]4,16]{\ displaystyle] 4.16]} |
3
|
]16,65536]{\ displaystyle] 16.65536]} |
4
|
]65536,265536]{\ displaystyle] 65536,2 ^ {65536}]} |
5
|
Proprietăți
Această funcție crește extrem de lent. O funcție comună în informatica teoretică care crește și mai încet este reciprocă funcției lui Ackermann . Aceste două funcții sunt, de asemenea, legate, deoarece logaritmul iterat este unul dintre nivelurile ierarhiei reciproce a lui Ackermann.
Utilizări
Note și referințe
-
Gabriel Nivasch, " Ackermann invers fără durere " ,2009.
-
Secțiunea de referință a Linial: (în) Nathan Linial , „ Locality in Distributed Graph Algorithms ” , SIAM Journal on Computing , vol. 21, n o 1,1992, p. 193-201.
-
Sanjoy Dasgupta , Christos H. Papadimitriou și Umesh Vazirani , Algoritmi , McGraw-Hill, Inc.,13 septembrie 2006( ISBN 0073523402 și 9780073523408 , citiți online )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">