Itererad logaritm

En itererad logaritm i matematik och datavetenskap definieras som en heltalsfunktion lika med antalet iterativa logaritmer av argumentet som krävs för att göra resultatet mindre än eller lika med 1 . Denna funktion är definierad för alla positiva tal, men i applikationer är argumentet vanligtvis ett naturligt tal . En mer strikt itererad logaritm definieras av den rekursiva formeln: $\log ^{*}n$

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

Den itererade logaritmen definieras för baserna A073229 . Om är positivt , då konvergerar den rekursiva sekvensen som definierar den till ett tal större än 1. Inom datavetenskap används vanligtvis itererad binär logaritm. $b>e^{1/e}\approx 1{,}444667$ ${\displaystyle b<e^{1/e))$

Denna funktion växer i det oändliga, men extremt långsamt. För alla argument som är tänkbara i praktiken skulle den kunna ersättas med en konstant, men för formler definierade på hela den numeriska axeln skulle en sådan notation vara felaktig. Värdena för den binära itererade logaritmen för alla praktiskt intressanta argument överstiger inte 5 och ges nedan.

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

Applikation

Den itererade logaritmen uppstår i analysen av vissa algoritmer i uppskattningar av deras beräkningskomplexitet [5][4][3]]2 []1[ - [6] $O(n\log n\cdot 2^{O(\log ^{*}n)})$ $n$ $O(\log ^{*}n)$

Anteckningar

↑ Olivier Devillers, "Randomisering ger enkla O(n log* n)-algoritmer för svåra ω(n)-problem." International Journal of Computational Geometry & Applications 2:01 (1992), sid. 971-11.
↑ Noga Alon och Yossi Azar, "Hitta ett ungefärligt maximum". SIAM Journal of Computing 18 :2 (1989), sid. 2582-67.
↑ Om separatorer, segregatorer och tid mot utrymme . Hämtad 31 augusti 2015. Arkiverad från originalet 25 juni 2012. (obestämd)
↑ Robert Sedgewick - Robert Sedgewick . Hämtad 31 augusti 2015. Arkiverad från originalet 8 mars 2021. (obestämd)
↑ Schneider, J. (2008), A log-star distributed maximal independent set algorithm for growth-bounded graphs , Proceedings of the Symposium on Principles of Distributed Computing Arkiverad 30 juli 2013 på Wayback Machine
↑ Richard Cole och Uzi Vishkin: "Deterministic coin tossing with applications to optimal parallell list ranking", Information and Control 70:1(1986), s. 325-3.