Iterovaný logaritmus

Iterovaný logaritmus v matematice a informatice je definován jako celočíselná funkce rovnající se počtu iteračních logaritmů argumentu požadovaných k tomu, aby byl výsledek menší nebo rovný 1 . Tato funkce je definována pro všechna kladná čísla, ale v aplikacích je argumentem obvykle přirozené číslo . Přesněji iterovaný logaritmus je definován rekurzivním vzorcem: $\log ^{*}n$

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

Iterovaný logaritmus je definován pro báze A073229 . Pokud je kladné , pak rekurzivní posloupnost, která ji definuje, konverguje k číslu většímu než 1. V informatice se obvykle používá iterovaný binární logaritmus. $b>e^{1/e}\cca 1{,}444667$ ${\displaystyle b<e^{1/e))$

Tato funkce roste donekonečna, ale extrémně pomalu. U všech v praxi myslitelných argumentů by se dala nahradit konstantou, ale u vzorců definovaných na celé číselné ose by byl takový zápis chybný. Hodnoty binárního iterovaného logaritmu pro všechny prakticky zajímavé argumenty nepřesahují 5 a jsou uvedeny níže.

n	$\log _{2}^{*}n$
(−∞, 1]	0
(12]	jeden
(2, 4]	2
(4, 16]	3
(16, 65536]	čtyři
(65536, 2 65536 (~10 19660 )]	5

Aplikace

Iterovaný logaritmus vzniká při analýze některých algoritmů při odhadech jejich výpočetní [5][4][3]]2 []1[složitosti - [6] $O(n\log n\cdot 2^{O(\log ^{*}n)})$ $n$ $O(\log ^{*}n)$

Poznámky

↑ Olivier Devillers, "Randomizace poskytuje jednoduché O(n log* n) algoritmy pro obtížné ω(n) problémy." International Journal of Computational Geometry & Applications 2:01 (1992), str. 971-11.
↑ Noga Alon a Yossi Azar, „Hledání přibližného maxima“. SIAM Journal of Computing 18 :2 (1989), str. 2582-67.
↑ O separátorech, rozdělovačích a čase versus prostor . Získáno 31. srpna 2015. Archivováno z originálu 25. června 2012. (neurčitý)
↑ Robert Sedgewick - Robert Sedgewick . Získáno 31. srpna 2015. Archivováno z originálu dne 8. března 2021. (neurčitý)
↑ Schneider, J. (2008), Log-star distribuovaný algoritmus maximálních nezávislých množin pro grafy ohraničené růstem , Sborník příspěvků ze sympozia o principech distribuovaného počítání archivováno 30. července 2013 na Wayback Machine
↑ Richard Cole a Uzi Vishkin: „Deterministické házení mincí s aplikacemi k optimálnímu hodnocení paralelních seznamů“, Information and Control 70:1 (1986), str. 325-3.