Co to jest O (log * N)?

80

Co to jest O (log * N) i czym się różni od O (log N)?

Timmy
źródło
Podobne pytanie: stackoverflow.com/questions/2307283/ ...O(log* N) Niestety brak odpowiedzi .
BalusC
1
Czy jest to pytanie o znak * po logu czy ogólnie o notację O ()?
Bart van Heukelom
1
Znajduje się w niektórych zaawansowanych strukturach danych, ale jestem poza szkołą zbyt długo, by przypomnieć sobie, skąd pochodzi!
Larry,
1
Chyba nie tak zaawansowany, po prostu zapamiętany - Union Find z początkową dolną granicą kompresji ścieżki został ustawiony na O (n log * n), dopóki nie został obniżony do O (A n), gdzie A jest odwrotną funkcją Ackermanna ..
Larry
1
Heh. W praktyce myślę, że byłbym zadowolony z oszacowania O (n). :-)
RBarryYoung

Odpowiedzi:

84

O( log* N )jest „ logarytmem iterowanym ”:

W informatyce iterowany logarytm n, zapisany log * n (zwykle czytany jako „log star”), to liczba razy, gdy funkcja logarytm musi być iteracyjnie zastosowana, zanim wynik będzie mniejszy lub równy 1.

Larry
źródło
9
To naprawdę interesująca rzecz, o której nie słyszałem. Q + A +1 każdy. Myślę, że O (log * N) jest dla wszystkich zamiarów i celów O (1). Fajne.
Greg
1
@greg, brak logu (n) oznacza, że ​​wraz ze wzrostem liczby elementów czas jest wolniejszy. na przykład. 10x więcej elementów sprawia, że ​​funkcja trwa 2 razy dłużej
Martin Beckett
2
Myślę, że po raz pierwszy natknąłem się na to podczas analizy algorytmu Union-Find, O( N log* N )zanim został ulepszony do O( A N ), gdzie A jest odwrotną funkcją Ackermanna. Wciąż nie rozumiem tego ostatniego dowodu, ale O( N log* N )algorytm jest stosunkowo dobry do czytania.
Larry,
13
@Martin, ale to jest log * (n), który rośnie szalenie powoli, tak że log * (2 ^ 65536 -1) = 5. Równie dobrze możesz wywołać tę stałą.
Greg
4
Przepraszam, że nie doceniłem różnicy log-star, dzięki - nauczyłem się czegoś nowego!
Martin Beckett
25

log* NNieco to powtórzyć algorytm, który rośnie bardzo powoli, znacznie wolniej niż po prostu log N. Zasadniczo po prostu powtarzasz „rejestrowanie” odpowiedzi, dopóki nie spadnie poniżej jednego (np .:) log(log(log(...log(N))), a liczba razy, którą musiałeś, log()jest odpowiedzią.

W każdym razie jest to pytanie sprzed pięciu lat na temat Stackoverflow, ale brak kodu? (!) Naprawmy to - oto implementacje dla funkcji rekurencyjnych i iteracyjnych (obie dają ten sam wynik):

public double iteratedLogRecursive(double n, double b)
{
    if (n > 1.0) {
        return 1.0 + iteratedLogRecursive( Math.Log(n, b),b );
    }
    else return 0;
}

public int iteratedLogIterative(double n, double b)
{
    int count=0;
    while (n >= 1) {
        n = Math.Log(n,b);
        count++;
    }
    return count;
}
Dan W
źródło
2
Jak to odpowiada na pytanie?
Maroun
3
@MarounMaroun: Zredagowałem początek odpowiedzi, aby nadać szerszy kontekst. Kod to opis / definicja, o którą prosił.
Dan W
9

log * (n) - "log Star n" znany jako "logarytm iterowany"

W prostym słowie możesz założyć log * (n) = log (log (log (..... (log * (n))))

log * (n) jest bardzo potężny.

Przykład:

1) Log * (n) = 5, gdzie n = liczba atomów we wszechświecie

2) Kolorowanie drzewa przy użyciu 3 kolorów można wykonać w log * (n), podczas gdy kolorowanie drzewka 2 kolory są wystarczające, ale złożoność będzie wynosić O (n).

3) Znalezienie triangulacji Delaunaya zbioru punktów ze znajomością minimalnego euklidesowego drzewa rozpinającego: losowy czas O (n log * n).

Manish Kumar
źródło