Iterowany logarytm - Iterated logarithm

W informatyce , w potwierdzili logarytmu z napisanej dziennika * (zwykle czytać „ gwiazdę dziennika ”), to ile razy logarytm funkcja musi być iteracyjnie stosowane przed wynik jest mniejszy niż lub równy . Najprostsza definicja formalna jest wynikiem tej relacji rekurencyjnej : ${\ Displaystyle n}$ ${\ Displaystyle n}$${\ Displaystyle 1}$

${\ Displaystyle \ log ^ {*} n: = {\ zacząć {przypadki} 0 i {\ mbox {jeśli}} n \ równa 1; \ \ 1 + \ log ^ {*} (\ log n) i {\ mbox {if }}n>1\end{przypadki}}}$

Na dodatnich liczbach rzeczywistych ciągły superlogarytm ( tetracja odwrotna ) jest zasadniczo równoważny:

${\ Displaystyle \ log ^ {*} n = \ lceil \ operatorname {slog} _ {e} (n) \ rceil}$

czyli podstawa b powtórzyć logarytm jest , jeśli n mieści się w przedziale , gdzie oznacza tetracja. Jednak dla ujemnych liczb rzeczywistych log-star jest , podczas gdy dla positive , więc obie funkcje różnią się dla argumentów ujemnych.${\ Displaystyle \ log ^ {*} n = y}$${\ Displaystyle ^ {y-1} b < n \ leq \ ^ {y} b}$${\ Displaystyle {^ {y} b} = \ underbrace {b ^ {b ^ {\ cdot ^ {\ cdot ^ {b}}}}} _ {y}}$${\ Displaystyle 0}$${\ Displaystyle \ lceil {\ tekst {slog}} _ {e} (-x) \ rceil = -1}$${\displaystyle x}$

Rysunek 1. Demonstracja log* 4 = 2 dla logarytmu iterowanego przy podstawie e. Wartość iterowanego logarytmu można znaleźć „zygzakiem” na krzywej y = log _b (x) od wejścia n do przedziału [0,1]. W tym przypadku b = e. Zygzakowatość pociąga za sobą rozpoczęcie od punktu (n, 0) i iteracyjne przejście do (n, log _b (n) ), do (0, log _b (n) ), do (log _b (n), 0 ).

Iterowany logarytm przyjmuje dowolną dodatnią liczbę rzeczywistą i daje liczbę całkowitą . Graficznie można to rozumieć jako liczbę „zygzaków” potrzebnych na rysunku 1 do osiągnięcia przedziału na osi x . ${\displaystyle [0,1]}$

W informatyce lg * jest często używany do wskazania binarnego iterowanego logarytmu , który iteruje logarytm binarny (o podstawie ) zamiast logarytmu naturalnego (o podstawie e ). ${\ Displaystyle 2}$

Matematycznie, iterowany logarytm jest dobrze zdefiniowany dla dowolnej podstawy większej niż , nie tylko dla podstawy i podstawy e . ${\ Displaystyle e ^ {1/e} \ około 1.444667}$${\ Displaystyle 2}$

Analiza algorytmów

Logarytm iterowany jest przydatny w analizie algorytmów i złożoności obliczeniowej , występującej w granicach złożoności czasowej i przestrzennej niektórych algorytmów, takich jak:

• Znalezienie triangulacji Delaunaya zbioru punktów znających minimalne euklidesowe drzewo rozpinające : czas randomizowany O ( n  log *  n ).
• Algorytm Fürera dla mnożenia liczb całkowitych: O( n  log  n  2 ^{O (lg *  n )} ).
• Znalezienie przybliżonego maksimum (element przynajmniej tak duży jak mediana): lg *  n − 4 do lg *  n + 2 operacje równoległe.
• Richard Cole uzi Vishkin „y rozmieszczone algorytm 3 barwienia o n -cycle : O ( log *  n ) synchronicznych rund komunikacyjnych.
• Wykonywanie ważonego szybkiego łączenia z kompresją ścieżki.

Iterowany logarytm rośnie bardzo wolno, znacznie wolniej niż sam logarytm. Dla wszystkich wartości n istotnych dla zliczania czasów działania algorytmów zaimplementowanych w praktyce (tj. n  ≤ 2 ⁶⁵⁵³⁶ , czyli znacznie więcej niż szacowana liczba atomów w znanym wszechświecie), iterowany logarytm o podstawie 2 ma wartość nie więcej niż 5.

Wyższe podstawy dają mniejsze iterowane logarytmy. Rzeczywiście, jedyną funkcją powszechnie używaną w teorii złożoności, która rośnie wolniej, jest odwrotna funkcja Ackermanna .

Inne aplikacje

Iterowany logarytm jest ściśle powiązany z uogólnioną funkcją logarytmiczną używaną w arytmetyce symetrycznego wskaźnika poziomu . Jest również proporcjonalna do trwałości addytywnej liczby , liczby przypadków , gdy ktoś musi zastąpić liczbę sumą jej cyfr, zanim osiągnie swój cyfrowy pierwiastek .

W teorii złożoności obliczeniowej Santhanam pokazuje, że zasoby obliczeniowe DTIME — czas obliczeń dla deterministycznej maszyny Turinga — i NTIME — czas obliczeń dla niedeterministycznej maszyny Turinga — są różne do${\ Displaystyle n {\ sqrt {\ log ^ {*} n}}.}$

Uwagi

Bibliografia

• Cormen, Thomas H .; Leiserson, Charles E. ; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. „3.2: Notacje standardowe i wspólne funkcje”. Wprowadzenie do algorytmów (wyd. 2). MIT Press i McGraw-Hill. s. 55-56. Numer ISBN 0-262-03293-7.