Qual è il significato di O (polilogo (n))? In particolare, come viene definito il polilogo (n)?

Question

Breve:
Quando i documenti accademici (informatici) dicono "O (polilogo (n))", cosa significano? Non sono confuso dal " Big-Oh " notazione, che conosco molto bene, ma piuttosto dalla funzione polylog (n). Non stanno parlando della complessa funzione di analisi Li _s (Z) Penso. O lo sono? Qualcosa di totalmente diverso forse?

Ulteriori dettagli:
Principalmente per interesse personale, recentemente ho esaminato vari articoli su Array di suffissi compressi, ad es. Vantaggi della ricerca all'indietro - Memoria secondaria efficiente e implementazione distribuita di array di suffissi compressi . Le stime di complessità computazionale dichiarate a volte riguardano il polilogo (n), che è una funzione che non conosco.

Wikipedia fornisce una definizione di polylog _s (z) che sembra riguardare principalmente l'analisi complessa e la teoria dei numeri analitici. Il mio sospetto è che non sia correlato al polilogo (n) nei documenti di compressione, anche se mi piacerebbe sentire diversamente da qualcuno più esperto. Se questo è il caso, perché si ritiene esattamente ragionevole omettere il pedice?

La mia unica altra ipotesi è che forse O (polilogo (n)) dovrebbe significare " Asintotico per una funzione polinomiale di log (n). " Ma questa è solo una supposizione: non ho prove di questo, e sarebbe un abuso di notazione per l'avvio.

In ogni caso, un collegamento a una definizione ragionevolmente autorevole sarebbe molto apprezzato!

Answer 1

Abuso di notazione o no, polilogo (n) significa "polinomio nel log (n)", proprio come "poli (n)" può significare "alcuni polinomi in n". Quindi O (polilogo (n)) significa " O ((log n) ^k ) per alcuni k " ;. (Vedi Wikipedia: Polylogarithmic o, per vederlo nel contesto, il blog del Prof. Scott Aaronson: < a href = "http://scottaaronson.com/blog/?p=263" rel = "noreferrer"> I miei tassi di crescita preferiti .)

Il punto è che proprio come spesso non ci interessiamo dei fattori costanti, è spesso conveniente ignorare i poteri dei logaritmi. A volte i "fattori di registro" vengono completamente ignorati e potresti vedere " & # 213; (f (n)) " & # 8212; & nbsp; O con una tilde sopra di essa & # 8212; che significa " O (f (n) polylog (f (n))) " ;, cioè, " O (f (n) (log f (n)) ^k ) per alcuni k " ;.

Answer 2

Il modo in cui viene utilizzato in questo documento sembra descrivere qualcosa come:

O (log ^ p n)

Answer 3

Polylog (n) è solo "polinomiale nel registro di n". Wikipedia

Answer 4

articolo polifunzionale diverso . Supponiamo che sia abbastanza vicino.

Answer 5

Sono sicuro che significano solo l'asse reale intero positivo: Re (n) = n

Answer 6

Wolfram ti offre una selezione , di cui la polilararitmo sembra più promettente.