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). :-)
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.
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;
}
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).
O(log* N)Niestety brak odpowiedzi .Odpowiedzi:
O( log* N )jest „ logarytmem iterowanym ”:źródło
O( N log* N )zanim został ulepszony doO( A N ), gdzie A jest odwrotną funkcją Ackermanna. Wciąż nie rozumiem tego ostatniego dowodu, aleO( N log* N )algorytm jest stosunkowo dobry do czytania.log* NNieco to powtórzyć algorytm, który rośnie bardzo powoli, znacznie wolniej niż po prostulog 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):
źródło
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).
źródło