Was ist O (log * N)?

80

Was ist O (log * N) und wie unterscheidet es sich von O (log N)?

algorithm math complexity-theory logarithm iterated-logarithm Timmy
quelle
Ähnliche Frage: stackoverflow.com/questions/2307283/… Leider keine Antwort auf O(log* N).
BalusC
1
Geht es bei dieser Frage um das * after log oder um die O () - Notation im Allgemeinen?
Bart van Heukelom
1
Es befindet sich in einigen fortgeschrittenen Datenstrukturen, obwohl ich zu lange nicht zur Schule gehe, um mich daran zu erinnern, woher es kommt!
Larry
1
Ich denke, nicht so weit fortgeschritten, nur daran erinnert - Union Find mit der anfänglichen Untergrenze der Pfadkomprimierung wurde auf O (n log * n) gesetzt, bis sie auf O (A n) gesenkt wurde, wobei A die inverse Ackermann-Funktion ist.
Larry
1
Heh. In der Praxis denke ich, dass ich mit einer Schätzung von O (n) dafür zufrieden wäre. :-)
RBarryYoung

Antworten:

84

O( log* N )ist " iterierter Logarithmus ":

In der Informatik ist der iterierte Logarithmus von n, geschriebenes log * n (normalerweise "loger Stern"), die Häufigkeit, mit der die Logarithmusfunktion iterativ angewendet werden muss, bevor das Ergebnis kleiner oder gleich 1 ist.

Larry
quelle
9
Das ist wirklich interessant, von dem ich noch nichts gehört habe. Q + A +1 jeweils. Ich denke, O (log * N) ist in jeder Hinsicht O (1). Cool.
Greg
1
@greg, kein Protokoll (n) bedeutet, dass mit zunehmender Anzahl der Elemente die Zeit langsamer steigt. z.B. 10x so viele Elemente lassen die Funktion nur 2x so lange dauern
Martin Beckett
2
Ich glaube, ich bin zum ersten Mal in der Analyse des Union-Find-Algorithmus darauf gestoßen, als er O( N log* N )vor seiner Verbesserung auf O( A N )A umgestellt wurde , wobei A die inverse Ackermann-Funktion ist. Ich verstehe den letzteren Beweis immer noch nicht, aber der O( N log* N )Algorithmus ist eine relativ gute Lektüre.
Larry
13
@Martin, aber das ist log * (n), das verrückt langsam ansteigt, so dass log * (2 ^ 65536 -1) = 5. Sie können diese Konstante auch nennen.
Greg
4
Tut mir leid, ich hatte den Unterschied zwischen den Log-Stars nicht gewürdigt, danke - etwas Neues gelernt!
Martin Beckett
25

Das log* NBit ist ein iterierter Algorithmus, der sehr langsam wächst, viel langsamer als nur log N. Sie protokollieren die Antwort im Grunde nur iterativ, bis sie unter eins log(log(log(...log(N)))fällt (zB :) , und die Häufigkeit, mit der Sie log()die Antwort benötigen, ist die Antwort.

Wie auch immer, dies ist eine fünf Jahre alte Frage zu Stackoverflow, aber kein Code? (!) Lassen Sie uns das beheben - hier sind Implementierungen für die rekursiven und iterativen Funktionen (beide liefern das gleiche Ergebnis):

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.
quelle
2
Wie beantwortet dies die Frage?
Maroun
3
@MarounMaroun: Ich habe den Anfang der Antwort bearbeitet, um mehr Kontext zu geben. Der Code ist die Beschreibung / Definition, nach der er gefragt hat.
Dan W
9

log * (n) - "log Star n" , bekannt als "Iterierter Logarithmus"

In einfachen Worten können Sie log * (n) = log (log (log (..... (log * (n)))) annehmen.

log * (n) ist sehr mächtig.

Beispiel:

1) Log * (n) = 5 wobei n = Anzahl der Atome im Universum

2) Das Färben von Bäumen mit 3 Farben kann in log * (n) erfolgen, während das Färben von Baum 2-Farben ausreicht, die Komplexität dann jedoch O (n) beträgt.

3) Finden der Delaunay-Triangulation einer Menge von Punkten, die den euklidischen minimalen Spannbaum kennen: randomisierte O (n log * n) -Zeit.

Manish Kumar
quelle