Was bedeutet "log*" zu bedeuten?

Habe ich auf den Begriff gekommen O(log* N) in einem Buch lese ich über Daten-Strukturen. Was bedeutet log* bedeuten? Ich kann nicht finden Sie es auf Google, und WolframAlpha versteht es nicht, entweder.

  • "Ich kann ihn nicht finden auf Google". Googeln mit 'log-Sterne -' funktioniert gut.
  • versuchen Sie "iterierten Logarithmus von x von 0 bis 6" oder "IteratedLog(4)" in WolframAlpha
  • Mögliche Duplikate von Was ist in O(log* N)?
InformationsquelleAutor pauldoo | 2010-09-26
  1. 23

    Es ist iterierten Logarithmus. Sehen hier für eine Beschreibung der vielen verschiedenen Zeit-Komplexität und hier für mehr details auf den iterierten Logarithmus selbst.

    Des iterierten Logarithmus ist die Anzahl der Zeiten, die der Logarithmus angewandt werden, bevor das Ergebnis wird ein oder weniger.

    InformationsquelleAutor paxdiablo
  2. 26

    Es heißt iterierten Logarithmus-Funktion. Es ist eine sehr langsam wachsende Funktion. Zum Beispiel:

    • lg*(2) = 1
    • lg*(4) = 2
    • lg*(16) = 3
    • lg*(65536) = 4
    • lg*(2^65536) = 5 /beachten Sie, dass (2^65536) ist viel größer als die Anzahl der Atome im beobachtbaren Universum/

    Oder im Fall von Big O könnte es ziemlich viel sein, als Konstante Zeit.

    • Mehr kurz und bündig, die iterierten Logarithmus zählt die Anzahl der Zeiten, die Sie haben, um den Logarithmus zu verringern einer Zahl um 1.
    • Also die inverse wäre iterierten Errichtung in die Stufe, welche ist die nächste in der Reihenfolge: addition, Multiplikation (=iterierten addition), Potenzierung (=iterierten Multiplikation), ...
    • Hmm, was ist mit iteration iteriert...
    InformationsquelleAutor Darin Dimitrov
  3. 5

    log* (n)- "log Stern von n" als bekannt als "Iterierten Logarithmus"

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

    log* (n) ist sehr mächtig.

    Beispiel:

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

    2) Baum-Färbung mit 3 Farben getan werden kann, im log*(n), während die Färbung Baum 2 Farben sind genug, aber Komplexität O(n) dann.

    3) die Suche nach der Delaunay-triangulation einer Menge von Punkten zu wissen, der euklidische minimum spanning tree: randomized O(n log* n) Zeit.

    Ich hoffe, Sie können Visualisieren Log* (n) wie diese auf WolframAlpha Überprüfen Sie hier

    InformationsquelleAutor Manish Kumar
  4. 2

    log* ist die Anzahl der Zeiten, die Sie müssen, um die log-Funktion, bis Sie erreichen einen Wert, der kleiner oder gleich 1 ist. Zum Beispiel: log*(16) = 3, denn log2(log2(log2(16))) = 1.

    Für praktische Zwecke können Sie behandeln Sie wie eine Konstante, da diese Funktion wächst sehr langsam.

    InformationsquelleAutor Harry Berry
Schreibe einen Kommentar