Logaritm iterat

Un logaritm iterativ în matematică și informatică este definit ca o funcție întreagă egală cu numărul de logaritmi iterativi ai argumentului necesar pentru a face rezultatul mai mic sau egal cu 1 . Această funcție este definită pentru toate numerele pozitive, dar în aplicații argumentul este de obicei un număr natural . Un logaritm mai strict iterat este definit de formula recursivă: $\log ^{*}n$

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

Logaritmul iterat este definit pentru bazele A073229 . Dacă este pozitiv , atunci secvența recursivă care o definește converge către un număr mai mare decât 1. În informatică, se folosește de obicei logaritmul binar iterat. $b>e^{1/e}\approx 1{,}444667$ $b<e^{1/e)$

Această funcție crește la nesfârșit, dar extrem de lent. Pentru toate argumentele imaginabile în practică, ar putea fi înlocuită cu o constantă, dar pentru formulele definite pe toată axa numerică, o astfel de notație ar fi eronată. Valorile logaritmului binar iterat pentru toate argumentele practic interesante nu depășesc 5 și sunt date mai jos.

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

Aplicație

Logaritmul iterat apare în analiza unor algoritmi în estimări ale complexității lor computaționale [5][4][3]]2 []1[ - [6] $O(n\log n\cdot 2^{O(\log ^{*}n)})$ $n$ $O(\log ^{*}n)$

Note

↑ Olivier Devillers, „Randomization yields simpli O(n log* n) algoritmi for dificil ω(n) problems.” International Journal of Computational Geometry & Applications 2:01 (1992), pp. 971-11.
↑ Noga Alon și Yossi Azar, „Găsirea unui maxim aproximativ”. SIAM Journal of Computing 18 :2 (1989), pp. 2582-67.
↑ Despre Separatoare, Segregatoare și Timp versus spațiu . Preluat la 31 august 2015. Arhivat din original la 25 iunie 2012. (nedefinit)
↑ Robert Sedgewick - Robert Sedgewick . Preluat la 31 august 2015. Arhivat din original la 8 martie 2021. (nedefinit)
↑ Schneider, J. (2008), A log-star distributed maximal independent set algorithm for growth-bounded graphs , Proceedings of the Symposium on Principles of Distributed Computing Arhivat la 30 iulie 2013 la Wayback Machine
^ Richard Cole și Uzi Vishkin : „Deterministic coin tossing with applications to optimal parallel list ranking”, Information and Control 70:1 (1986), pp. 325-3.