Co to jest O (log * N)?

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

Czy jest to pytanie o znak * po logu czy ogólnie o notację O ()?

— Bart van Heukelom

Znajduje się w niektórych zaawansowanych strukturach danych, ale jestem poza szkołą zbyt długo, by przypomnieć sobie, skąd pochodzi!

— Larry,

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

Heh. W praktyce myślę, że byłbym zadowolony z oszacowania O (n). :-)

— RBarryYoung

Odpowiedzi:

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

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

@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

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,

@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

Przepraszam, że nie doceniłem różnicy log-star, dzięki - nauczyłem się czegoś nowego!

— Martin Beckett

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

Jak to odpowiada na pytanie?

— Maroun

@MarounMaroun: Zredagowałem początek odpowiedzi, aby nadać szerszy kontekst. Kod to opis / definicja, o którą prosił.

— Dan W

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