Logaritmo iterato
In informatica , il logaritmo iterato di un numero n , annotato (leggi "stella del registro" o "stella del registro"), è il numero di volte in cui il logaritmo deve essere applicato prima che il risultato sia minore o uguale a 1. Questo viene utilizzata per descrivere la complessità di alcuni algoritmi, specialmente negli algoritmi distribuiti .
Definizione
Il logaritmo iterato in base b può essere definito da:
Su numeri reali positivi, il super-logaritmo continuo ( in) (l'inverso della tetrazione ) è essenzialmente equivalente:
La tabella seguente fornisce i valori del logaritmo iterato (in base 2):
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 |
![{\ displaystyle] - \ infty; 1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/edfc3ee458eec4169c3788c27a6955b3013a2706)
![{\ displaystyle] 1,2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2545c2ae6bb7fa4444175fe644fa2e4dbfe3ec2)
![{\ displaystyle] 2,4]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/15f612a16960e64caa44ba64284e443be479eec4)
![{\ displaystyle] 4.16]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/741160006f2c5fba6e49c8555db27f25a604744a)
![{\ displaystyle] 16.65536]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68bd491c79b17bd294fbfefd9310d16ddd3f3392)
![{\ displaystyle] 65536,2 ^ {65536}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1905c450fdf37c5835cf234989afd13516e382f6)
Proprietà
Questa funzione sta crescendo molto lentamente. Una funzione comune nell'informatica teorica che cresce ancora più lentamente è il reciproco della funzione di Ackermann . Queste due funzioni sono anche correlate, poiché il logaritmo iterato è uno dei livelli della gerarchia del reciproco di Ackermann.
Utilizza
- Questa funzione viene utilizzata per l'analisi dell'algoritmo, ad esempio per esprimere la complessità dell'algoritmo di triangolazione di Delaunay e negli algoritmi distribuiti, ad esempio nel limite inferiore lineare per la colorazione dei grafi .
- Dasgupta et al., Nel loro libro algoritmico, presentano un'analisi della complessità smorzata della struttura dei dati di ritrovamento dell'unione utilizzando il logaritmo iterato.
- Il logaritmo iterato è coinvolto nella complessità dell'algoritmo di Fürer .
Note e riferimenti
- Gabriel Nivasch, " Ackermann inverso senza dolore " ,2009.
- Sezione di riferimento di Linial: (in) 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 e Umesh Vazirani , Algorithms , McGraw-Hill, Inc.,13 settembre 2006( ISBN 0073523402 e 9780073523408 , leggi online )