Itereret logaritme
I datalogi er den itererede logaritme for et tal n , bemærket (læs "log-stjerne" eller "log-stjerne"), det antal gange logaritmen skal anvendes på den, før resultatet er mindre end eller lig med 1. Dette funktion bruges til at beskrive kompleksiteten af visse algoritmer, især i distribuerede algoritmer .
Definition
Den base, itereret logaritme b kan defineres ved:
På positive reelle tal er den kontinuerlige ( in) superlogaritme (det omvendte af indtrængningen ) i det væsentlige ækvivalent:
Følgende tabel giver værdierne for den itererede logaritme (i 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)
Ejendomme
Denne funktion vokser ekstremt langsomt. En fælles funktion inden for teoretisk datalogi, der vokser endnu langsommere, er gensidigheden af Ackermanns funktion . Disse to funktioner er også relateret, da den itererede logaritme er et af niveauerne i hierarkiet af Ackermanns gensidige.
Anvendelser
- Denne funktion bruges til analyse af algoritmer, for eksempel til at udtrykke kompleksiteten af Delaunay-triangulationsalgoritmen og i distribueret algoritme, for eksempel i den nedre grænse for Linial til graffarvning .
- Dasgupta et al. I deres algoritmiske bog præsenterer en dæmpet kompleksitetsanalyse af union-find- datastrukturen ved hjælp af den itererede logaritme.
- Den itererede logaritme er involveret i kompleksiteten af Fürers algoritme .
Noter og referencer
- Gabriel Nivasch, " Invers Ackermann uden smerte " ,2009.
- Referenceafsnit i Linial: (in) Nathan Linial , " Lokalitet i distribuerede grafalgoritmer " , SIAM Journal on Computing , vol. 21, nr . 1,1992, s. 193-201.
- Sanjoy Dasgupta , Christos H. Papadimitriou og Umesh Vazirani , Algorithms , McGraw-Hill, Inc.,13. september 2006( ISBN 0073523402 og 9780073523408 , læs online )