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

Breve:
Quando gli articoli accademici (informatica) dicono "O (polylog (n))", cosa significano? Non sono confuso dalla notazione "Big-Oh", che mi è molto familiare, ma piuttosto dalla funzione polylog (n). Non stanno parlando della complessa funzione di analisi Li_s(Z) Penso. O sono loro? Forse qualcosa di completamente diverso?Qual è il significato di O (polylog (n))? In particolare, come viene definito il polylog (n)?

Più particolare:
Per lo più per interesse personale, ho recentemente cercato su varie carte sulla compressa suffisso Array, ad esempio, Advantages of Backward Searching -- Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays. Le stime di complessità computazionale dichiarate a volte coinvolgono polylog (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 è collegato al polylog (n) nei documenti di compressione, anche se mi piacerebbe sentire diversamente da qualcuno più esperto. Se questo è il caso, perché è ragionevole pensare di omettere l'indice?

La mia unica altra ipotesi è che forse O (polylog (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 ad una definizione ragionevolmente autorevole sarebbe molto apprezzato!

fonte

2009-11-26 Managu

Dove l'hai visto? –

Nell'estratto collegato, viene indicato "... il CSA può essere cercato nel tempo O (m) ogni volta che = O (polylog (n))." – Managu

Oh, forse Sadakane [SODA 2002] ha la tua risposta definitiva. –

Abuso di notazione o no, polylog (n) significa "qualche polinomio in log (n)", così come "poli (n)" può significare "alcuni polinomiale in n". Quindi O (polylog (n)) significa "O ((log n) ^k) per alcuni k". (Vedere Wikipedia: Polylogarithmic, o, per vederlo in contesto, il blog del Prof. Scott Aaronson:. My Favorite Growth Rates)

Il punto è che, proprio come spesso non ci preoccupiamo per fattori costanti, è spesso conveniente ignorare i poteri dei logaritmi . A volte i "fattori di log" vengono ignorati del tutto e potresti vedere "Õ (f (n))" - O con una tilde sopra di esso - che means "O (f (n) polylog (f (n)))", cioè , "O (f (n) (log f (n)) ^k) per alcuni k".

fonte

2009-11-26 01:55:02 ShreevatsaR

Abbastanza giusto. Grazie per i link! – Managu

'Spesso è conveniente ignorare i poteri dei logaritmi '. Strano. In che modo ignorare i poteri dei logaritmi può essere conveniente quando cambia completamente significato? – Lazer

@eSKay: allo stesso modo è spesso conveniente ignorare i fattori costanti anche se cambia completamente significato: dipende solo da ciò su cui si desidera concentrarsi. Qualsiasi funzione polilogaritmica cresce più lentamente di O (n^ε) per * ogni * ε. Quindi quando ciò che ti interessa è l'esponente in n - e.g. cercando di distinguere tra n^2.1 e n^2 - questi fattori poliloghi non contano. O (n^2 polylog (n)) è O (n^(2 + ε)) per tutti ε, quindi scriviamo Õ (n^2). – ShreevatsaR