Was ist die Bedeutung von O (polylog (n))? Insbesondere wird, wie PolyLog (n) definiert?

Question

Kurz:
Wenn akademische (Informatik) Papiere sagen: "O (polylog (n))", was bedeuten sie? Ich bin nicht von der „Big-Oh“ Notation, die ich bin sehr vertraut mit, sondern vielmehr durch die Funktion polylog (n) verwechselt. Sie sprechen nicht über die komplexe Analysefunktion Li _s (Z) ich denke. Oder sind Sie? Etwas ganz anderes vielleicht?

Weitere Einzelheiten:
Vor allem für persönliches Interesse habe ich verschiedene Papiere auf Compressed Suffixarray suche über, zum Beispiel vor kurzem Vorteile der Rückwärtssuche - Effiziente Sekundärspeicher und verteilte Implementierung von Compressed Suffixarray . Die Rechenkomplexität Schätzungen angegeben manchmal polylog (n) umfassen, die eine Funktion, die ich nicht kenne.

Wikipedia gibt eine Definition von polylog _s (z) die erscheint in erster Linie um eine komplexe Analyse und analytischen Zahlentheorie zu sein. Mein Verdacht ist, dass es nicht auf die polylog (n) in den Kompressions Papieren in engen Zusammenhang steht, obwohl ich von jemandem kenntnis sonst gerne hören würde. Wenn dies der Fall ist, warum genau es ist, dachte sinnvoll, den Index zu verzichten?

Meine einzige andere Vermutung ist, dass vielleicht O (polylog (n)) bedeuten soll „asymptotisch zu einer Polynom-Funktion von log (n).“ Aber das ist nur eine Vermutung. Ich habe keine Beweise dafür, und es wäre ein Missbrauch der Notation Boot sein

Auf jedem Fall ein Link zu einer einigermaßen verbindlichen Definition wäre sehr dankbar!

Answer 1

Missbrauch der Notation oder nicht, polylog (n) bedeutet "einige Polynom in log (n)", ebenso wie "Poly (n)" kann "ein Polynom in n" bedeuten. So O (polylog (n)) bedeutet "O ((log n) ^k ) für ein k". (Siehe Wikipedia: polylogarithmischen , oder, um es im Kontext zu sehen, Blog Prof. Scott Aaronson ist: < a href = "http://scottaaronson.com/blog/?p=263" rel = "noreferrer"> My Favorite Wachstumsraten .)

Der Punkt ist, dass so wie wir oft über konstante Faktoren nicht kümmern, ist es oft bequem Kräfte der Logarithmen zu ignorieren. Manchmal ist die "log Faktoren" werden ignoriert vollständig und Sie könnten "Õ (f (n))" sehen - O mit einer Tilde darüber - die a href <= "http://en.wikipedia.org/wiki/%C3 95" % rel = "noreferrer"> bedeutet "O (f (n) polylog (f (n)))", dh „O (f (n) (log f (n)) ^k ) für ein k“.

Answer 2

So wie es verwendet wird, in diesem Papier scheint etwas so zu beschreiben:

O (log p ^ n)

Answer 3

Polylog (n) nur "Polynom im Protokoll von n". Wikipedia

Answer 4

polylog Artikel . Sie sind Vermutung sehr nahe ist.

Answer 5

Ich bin sicher, sie bedeuten nur die positive ganze Zahl reellen Achse: Re(n) = n

Answer 6

Wolfram gibt Ihnen eine Auswahl , von denen die Polylogarithmus Seite sieht sehr vielversprechend aus.