Quelle est la signification de O (polylog (n))? En particulier, comment définit-on polylog (n)?

Question

Mémoire:
Lorsque des documents universitaires (en informatique) disent "O (polylog (n))", que veulent-ils dire? Je ne suis pas déconcerté par le message "Big-Oh". notation, que je connais très bien, mais plutôt par la fonction polylog (n). Ils ne parlent pas de la fonction d'analyse complexe Li _s (Z) Je pense. Ou sont-ils? Quelque chose de totalement différent peut-être?

Plus en détail:
Principalement pour des raisons d’intérêt personnel, j’ai récemment examiné divers documents sur les tableaux de suffixes compressés, par exemple. Avantages de la recherche arrière - Mémoire secondaire efficace et implémentation distribuée de tableaux de suffixes compressés . Les estimations de complexité de calcul mentionnées impliquent parfois polylog (n), fonction que je ne connais pas bien.

Wikipedia donne une définition de polylog _s (z) , qui semble concerner principalement l’analyse complexe et la théorie analytique des nombres. Je soupçonne que cela n’est pas lié au polylog (n) dans les papiers de compression, bien que j'aimerais entendre parler autrement de quelqu'un de plus au courant. Si tel est le cas, pourquoi pense-t-on qu'il est raisonnable d'omettre l'indice?

Ma seule autre hypothèse est que peut-être O (polylog (n)) est supposé signifier "Asymptotique à une fonction polynomiale de log (n)." Mais ce n’est qu’une hypothèse: je n’ai aucune preuve de cela, et ce serait un abus de notation que de démarrer.

Dans tous les cas, un lien vers une définition faisant raisonnablement autorité serait grandement apprécié!

Answer 1

Abus de notation ou non, polylog (n) signifie "un polynôme dans log (n)", tout comme "poly (n)". peut signifier "un polynôme dans n". Donc, O (polylog (n)) signifie "O ((log n) ^k )" pour un certain k ". (Voir Wikipedia: Polylogarithmic ou, pour le mettre en contexte, le blog du professeur Scott Aaronson: < a href = "http://scottaaronson.com/blog/?p=263" rel = "noreferrer"> Taux de croissance de mes favoris .)

Le fait est que, tout comme nous ne nous soucions pas souvent de facteurs constants, il est souvent commode d’ignorer les pouvoirs des logarithmes. Parfois, les "facteurs de journalisation" sont totalement ignorés et vous pourriez voir "& # 213; (f (n))" & & # 8212; & nbsp; O avec un tilde au-dessus de celui-ci & # 8212; qui signifie " O (f (n) polylog (f (n))) ", c'est-à-dire," O (f (n) (log f (n)) ^k ) pour un certain k ".

Answer 2

La manière dont il est utilisé dans cet article semble décrire quelque chose comme:

O (log ^ p n)

Answer 3

Polylog (n) est juste un "polynôme dans le log de n". Wikipedia

Answer 4

Différent article de polylog . Vous devinez est assez proche.

Answer 5

Je suis sûr qu'ils désignent uniquement l'axe réel entier positif: Re (n) = n

Answer 6

Wolfram vous propose une sélection , dont le polylogarithme est très prometteur.