Logaritm iterat

În informatică , logaritmul iterat al lui n , log scris * n (de obicei citește „ asterisc jurnal ”), este de câte ori funcția logaritmului trebuie aplicată iterativ înainte ca rezultatul să fie mai mic sau egal cu 1. Cea mai simplă definiție formală este rezultatul acestei funcții recursive:

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

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

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

Pe numere reale pozitive, continuă superlogarithm (invers tetration ) este , în esență echivalent:

\log ^{*}n=\lceil {\text{slog}}_{e}(n)\rceil

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

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

dar pentru numerele reale negative, jurnal-asterisc este 0, în timp ce $\lceil {\text{slog}}_{e}(-x)\rceil =-1$ ${\ displaystyle \ lceil {\ text {slog}} _ {e} (- x) \ rceil = -1}$ ${\ displaystyle \ lceil {\ text {slog}} _ {e} (- x) \ rceil = -1}$ pentru x pozitiv, deci cele două funcții diferă pe argumente negative.

Figura 1. Dovada lg * 4 = 2

În informatică, lg- * este adesea folosit pentru a desemna logaritmul binar iterat, care iterează în schimb logaritmul binar . Logaritmul iterat acceptă orice număr real pozitiv și produce un număr întreg . Grafic, poate fi înțeles ca numărul de "zigzaguri" necesare în Figura 1 pentru a atinge intervalul [0, 1] pe axa x .

Matematic, logaritmul iterat este bine definit nu numai pentru baza 2 și baza e , ci pentru orice bază mai mare de $e^{1/e}\approx 1,444667$ ${\ displaystyle e ^ {1 / e} \ aproximativ 1.444667}$ ${\ displaystyle e ^ {1 / e} \ aproximativ 1.444667}$ .

Analiza algoritmilor

Logaritmul iterat este util în analiza algoritmilor și în complexitatea de calcul , apărând în limitele complexității temporale și spațiale a unor algoritmi precum:

Găsiți triangulația Delaunay a unui set de puncte cunoscând arborele minim euclidian : interval aleatoriu O ( n log * n ) ^[1]
Algoritmul lui Fürer pentru multiplicarea numerelor întregi: O ( n log n 2 ^{lg * n} )
Găsiți un maxim aproximativ (element cel puțin la fel de mare ca mediana): lg * n - 4 la lg * n + 2 operații paralele ^[2]
Algoritm distribuit pentru 3-colorarea unui ciclu n de Richard Cole și Uzi Vishkin : sesiuni de comunicare sincronă O (log * n ). ^[3] ^[4]

Logaritmul iterat crește într-un ritm extrem de lent, mult mai lent decât logaritmul în sine. Pentru toate valorile n relevante pentru numărarea timpilor de execuție a algoritmilor implementați în practică (adică n ≤ 2 ⁶⁵⁵³⁶ , care este de departe mai mare decât atomii universului cunoscut), logaritmul iterat cu baza 2 are o valoare care nu este depășind 5.

X	lg * x
(−∞, 1]	0
(1, 2)	1
(2, 4]	2
(4, 16)	3
(16, 65536]	4
(65536, 2 ⁶⁵⁵³⁶ ]	5

Bazele superioare dau logaritmi iterați mai mici. De fapt, singura funcție utilizată în mod obișnuit în cea mai lentă creștere a teoriei complexității este funcția inversă a lui Ackermann .

Alte aplicații

Logaritmul iterat este strâns legat de funcția logaritmică generalizată utilizată în aritmetică cu indici de nivel simetric . De asemenea, este proporțional cu persistența aditivă a unui număr , de câte ori numărul trebuie înlocuit cu suma cifrelor sale înainte de a ajunge la rădăcina sa numerică .

Santhanam ^[5] arată că DTIME și NTIME sunt distincte până la $n{\sqrt {\log ^{*}n}}.$ ${\ displaystyle n {\ sqrt {\ log ^ {*} n}}.}$ ${\ displaystyle n {\ sqrt {\ log ^ {*} n}}.}$

Notă

^ Olivier Devillers, "Randomizarea produce algoritmi simpli O (n log * n) pentru probleme dificile ω (n).". International Journal of Computational Geometry & Applications 2 : 01 (1992), pp. 97–111.
^ Noga Alon și Yossi Azar, „Găsirea unui maxim aproximativ”. SIAM Journal of Computing 18 : 2 (1989), pp. 258-267.
^ Richard Cole și Uzi Vishkin: "Aruncarea deterministă a monedelor cu aplicații pentru clasarea optimă a listelor paralele", Information and Control 70: 1 (1986), pp. 32-53.
^ * Thomas H. Cormen , Charles A. Leiserson , Ronald L. Rivest și Clifford Stein , Secțiunea 30.5 , în Introducere în algoritmi și structuri de date , ediția I, MIT Press și McGraw-Hill, 1990, ISBN 0-262- 03141 -8 .
^ Despre separatoare, segregatoare și timp versus spațiu

Bibliografie

Thomas H. Cormen , Charles A. Leiserson , Ronald L. Rivest și Clifford Stein , 3.2: Notări standard și funcții comune , în Introducere în algoritmi și structuri de date , ediția a II-a, MIT Press și McGraw-Hill, 2001 [1990] , pp. 55-56, ISBN 0-262-03293-7 .

Portal IT

Portalul de matematică

[1] Olivier Devillers, "Randomizarea produce algoritmi simpli O (n log * n) pentru probleme dificile ω (n).". International Journal of Computational Geometry & Applications 2 : 01 (1992), pp. 97–111.

[2] Noga Alon și Yossi Azar, „Găsirea unui maxim aproximativ”. SIAM Journal of Computing 18 : 2 (1989), pp. 258-267.

[3] Richard Cole și Uzi Vishkin: "Aruncarea deterministă a monedelor cu aplicații pentru clasarea optimă a listelor paralele", Information and Control 70: 1 (1986), pp. 32-53.

[4] * Thomas H. Cormen , Charles A. Leiserson , Ronald L. Rivest și Clifford Stein , Secțiunea 30.5 , în Introducere în algoritmi și structuri de date , ediția I, MIT Press și McGraw-Hill, 1990, ISBN 0-262- 03141 -8 .

[5] Despre separatoare, segregatoare și timp versus spațiu

[1]

[2]

[3]

[4]

[5]