Itereret logaritme

En itereret logaritme i matematik og datalogi er defineret som en heltalsfunktion svarende til antallet af iterative logaritmer af argumentet, der kræves for at gøre resultatet mindre end eller lig med 1 . Denne funktion er defineret for alle positive tal, men i applikationer er argumentet normalt et naturligt tal . En mere strengt itereret logaritme er defineret af den rekursive formel: $\log ^{*}n$

\log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leqslant 1;\\1+\log ^{*}(\log n)&{\mbox {if }}n>1\end{cases}}

Den itererede logaritme er defineret for baser A073229 . Hvis er positiv , så konvergerer den rekursive sekvens, der definerer den, til et tal, der er større end 1. Inden for datalogi bruges der normalt itereret binær logaritme. $b>e^{1/e}\approx 1{,}444667$ ${\displaystyle b<e^{1/e))$

Denne funktion vokser uendeligt, men ekstremt langsomt. For alle argumenter, der er tænkelige i praksis, kunne den erstattes af en konstant, men for formler defineret på hele den numeriske akse ville en sådan notation være fejlagtig. Værdierne af den binære itererede logaritme for alle praktisk talt interessante argumenter overstiger ikke 5 og er angivet nedenfor.

n	$\log _{2}^{*}n$
(−∞, 1]	0
(12]	en
(2, 4]	2
(4, 16]	3
(16, 65536]	fire
(65536, 2 65536 (~10 19660 )]	5

Ansøgning

Den itererede logaritme opstår i analysen af nogle algoritmer i estimater af deres beregningsmæssige [5][4][3]]2 []1[kompleksitet - [6] $O(n\log n\cdot 2^{O(\log ^{*}n)})$ $n$ $O(\log ^{*}n)$

Noter

↑ Olivier Devillers, "Randomisering giver simple O(n log* n) algoritmer til vanskelige ω(n) problemer." International Journal of Computational Geometry & Applications 2:01 (1992), pp. 971-11.
↑ Noga Alon og Yossi Azar, "At finde et omtrentligt maksimum". SIAM Journal of Computing 18 :2 (1989), pp. 2582-67.
↑ Om separatorer, segregatorer og tid versus rum . Hentet 31. august 2015. Arkiveret fra originalen 25. juni 2012. (ubestemt)
↑ Robert Sedgewick - Robert Sedgewick . Hentet 31. august 2015. Arkiveret fra originalen 8. marts 2021. (ubestemt)
↑ Schneider, J. (2008), A log-star distributed maximum independent set algoritme for growth-bounded graphs , Proceedings of the Symposium on Principles of Distributed Computing Arkiveret 30. juli 2013 på Wayback Machine
↑ Richard Cole og Uzi Vishkin: "Deterministisk møntkastning med applikationer til optimal parallellisterangering", Information and Control 70:1(1986), s. 325-3.