Was ist O (log * N)?

Question

Was ist O(log* N)?

Ich weiß Big-Oh, die log* ist unbekannt.

Answer 1

O(log* N) ist "iterated logarithm":

In der Informatik, der iterierten Logarithmus von n, geschrieben log * n (in der Regel "log Stern" lesen), ist die Anzahl der Male der Logarithmus-Funktion iterativ sein muss bevor das Ergebnis angewendet kleiner oder gleich 1.

Answer 2

log * (n) - "log Stern n" als

als "iterierten Logarithmus" bekannt ist 210

In einfachen Wort kann man davon ausgehen, log * (n) = log (log (log (..... (log * (n))))

log * (n) sehr mächtig ist.

Beispiel:

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

2) Baum Coloring 3 Farben verwendet, kann in log erfolgen * (n) Während der Färbung von Baum 2 Farben ausreichen, wird die Komplexität dann O (n) sein.

3) Finden der Delaunay-Triangulation einer Menge von Punkten mit Kenntnis des euklidischen minimalen Spannbaums: randomisierte O (n log * n) -Zeit.

Answer 3

Das log* N Bit ist ein iterierter Algorithmus, der sehr langsam wächst, viel langsamer als nur log N. Sie im Grunde nur iterativ "Logging" die Antwort, bis es unter eins kommt (z. B. log(log(log(...log(N)))), und die Anzahl der Male, die Sie hatten log() ist die Antwort.

Wie auch immer, dies ist eine fünf Jahre alte Frage auf Stackoverflow, aber kein Code Lassen Sie uns das in Ordnung bringen - hier Implementierungen sowohl für die rekursive und iterative Funktionen (sie beide 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; 
}