Iterovaný logaritmus - Iterated logarithm

v počítačová věda, iterovaný logaritmus z ${ displaystyle n}$ , psaný log* ${ displaystyle n}$ (obvykle číst „log hvězda"), je počet opakování logaritmus funkce musí být iterativně aplikován před výsledek je menší nebo roven ${ displaystyle 1}$ . Výsledkem je nejjednodušší formální definice relace opakování:

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

Na kladná reálná čísla, kontinuální super-logaritmus (inverzní tetování ) je v podstatě ekvivalentní:

{ displaystyle log ^ {*} n = lceil mathrm {slog} _ {e} (n) rceil}

tj. základna b iterovaný logaritmus je ${ displaystyle log ^ {*} n = y}$ pokud n leží v intervalu ${ displaystyle ^ {y-1} b$ , kde ${ displaystyle {^ {y} b} = podprsenka {b ^ {b ^ { cdot ^ { cdot ^ {b}}}}} _ {y}}$ označuje tetování. Avšak na záporných reálných číslech log-star je ${ displaystyle 0}$ , zatímco ${ displaystyle lceil { text {slog}} _ {e} (- x) rceil = -1}$ pro pozitivní ${ displaystyle x}$ , takže tyto dvě funkce se liší pro negativní argumenty.

Obrázek 1. Demonstrační log * 4 = 2 pro iterovaný logaritmus base-e. Hodnotu iterovaného logaritmu lze zjistit pomocí „cik cak“ na křivce y = log_b(x) od vstupu n do intervalu [0,1]. V tomto případě b = e. Zig-zagging znamená začít od bodu (n, 0) a iterativně se pohybovat k (n, log_b(n)), do (0, log_b(n)), do (log_b(n), 0).

Iterovaný logaritmus přijímá jakékoli kladné hodnoty reálné číslo a dává celé číslo. Graficky to lze chápat jako počet „cik caků“ potřebných v Obrázek 1 k dosažení intervalu ${ displaystyle [0,1]}$ na X-osa.

V počítačové vědě lg* se často používá k označení binární iterovaný logaritmus, který iteruje binární logaritmus (se základnou ${ displaystyle 2}$ ) místo přirozeného logaritmu (se základnou E).

Matematicky je iterovaný logaritmus dobře definován pro jakoukoli základnu větší než ${ displaystyle e ^ {1 / e} přibližně 1,444667}$ , nejen pro základnu ${ displaystyle 2}$ a základna E.

Analýza algoritmů

Iterovaný logaritmus je užitečný v analýza algoritmů a výpočetní složitost, které se objevují v mezích časové a prostorové složitosti některých algoritmů, například:

Nalezení Delaunayova triangulace ze sady bodů, které znají Euklidovský minimální kostra: randomizované Ó (n log* n) čas.^[1]
Fürerův algoritmus pro celočíselné násobení: O (n logn 2^Ó(lg* n)).
Nalezení přibližného maxima (prvek alespoň tak velký jako medián): lg* n - 4 až lg* n + 2 paralelní operace.^[2]
Richard Cole a Uzi Vishkin je distribuovaný algoritmus pro 3-barvení a n-cyklus: Ó(log* n) synchronní komunikační kola.^[3]^[4]
Provádění váženého rychlého spojení s kompresí cesty.^[5]

Iterovaný logaritmus roste extrémně pomalou rychlostí, mnohem pomaleji než samotný logaritmus. Pro všechny hodnoty n relevantní pro počítání doby chodu algoritmů implementovaných v praxi (tj. n ≤ 2⁶⁵⁵³⁶, což je mnohem více než odhadovaný počet atomů ve známém vesmíru), iterovaný logaritmus se základnou 2 má hodnotu ne větší než 5.

Iterovaný logaritmus základny-2
X	lg* X
(−∞, 1]	0
(1, 2]	1
(2, 4]	2
(4, 16]	3
(16, 65536]	4
(65536, 2⁶⁵⁵³⁶]	5

Vyšší báze dávají menší iterované logaritmy. Jedinou funkcí běžně používanou v teorii složitosti, která roste pomaleji, je inverzní Ackermannova funkce.

Další aplikace

Iterovaný logaritmus úzce souvisí s zobecněná logaritmická funkce použito v symetrická aritmetika indexu úrovně. Je také úměrná přísadě perzistence čísla, kolikrát musí někdo nahradit číslo součtem jeho číslic, než dosáhne svého digitální root.

v teorie výpočetní složitosti, Santhanam^[6] ukazuje, že výpočetní zdroje DTIME — výpočetní čas pro deterministický Turingův stroj - a NTIME - doba výpočtu pro a nedeterministický Turingův stroj - jsou odlišné až ${ displaystyle n { sqrt { log ^ {*} n}}.}$

Poznámky

^ Olivier Devillers, „Randomizace přináší jednoduché O (n log * n) algoritmy pro obtížné problémy s ω (n).“. International Journal of Computational Geometry & Applications 2: 01 (1992), s. 97–111.
^ Noga Alon a Yossi Azar, „Hledání přibližného maxima“. SIAM Journal on Computing 18: 2 (1989), str. 258–267.
^ Richard Cole a Uzi Vishkin: „Deterministické házení mincí s aplikacemi pro optimální hodnocení paralelních seznamů“, Information and Control 70: 1 (1986), str. 32–53.
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Úvod do algoritmů (1. vyd.). MIT Press a McGraw-Hill. ISBN 0-262-03141-8. Oddíl 30.5.
^ https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
^ Na oddělovačích, oddělovačích a času versus prostor

Reference

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "3.2: Standardní zápisy a běžné funkce". Úvod do algoritmů (2. vyd.). MIT Press a McGraw-Hill. str. 55–56. ISBN 0-262-03293-7.

[1] Olivier Devillers, „Randomizace přináší jednoduché O (n log * n) algoritmy pro obtížné problémy s ω (n).“. International Journal of Computational Geometry & Applications 2: 01 (1992), s. 97–111.

[2] Noga Alon a Yossi Azar, „Hledání přibližného maxima“. SIAM Journal on Computing 18: 2 (1989), str. 258–267.

[3] Richard Cole a Uzi Vishkin: „Deterministické házení mincí s aplikacemi pro optimální hodnocení paralelních seznamů“, Information and Control 70: 1 (1986), str. 32–53.

[4] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Úvod do algoritmů (1. vyd.). MIT Press a McGraw-Hill. ISBN 0-262-03141-8. Oddíl 30.5.

[5] ttps://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

[6] Na oddělovačích, oddělovačích a času versus prostor

[1]

[2]

[3]

[4]

[5]

[6]