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

Bref:
Lorsque les articles universitaires (informatique) disent “O (polylog (n))”, que veulent-ils dire? Je ne suis pas confondu par la notation “Big-Oh”, que je connais très bien, mais par la fonction polylog (n). Ils ne parlent pas de la fonction d’parsing complexe Li _s (Z) je pense. Ou sont-ils? Quelque chose de totalement différent peut-être?

Plus de détails:
Surtout pour mon intérêt personnel, j’ai récemment consulté divers articles sur les tableaux de suffixes compressés, par exemple les avantages de la recherche en arrière – la mémoire secondaire efficace et l’implémentation dissortingbuée des tableaux de suffixes compressés . Les estimations de complexité computationnelle indiquées impliquent parfois un polylog (n), fonction que je ne connais pas bien.

Wikipedia donne une définition de polylog _s (z) qui semble être principalement une parsing complexe et une théorie analytique des nombres. Mon soupçon est que ce n’est pas lié au polylog (n) dans les papiers de compression, bien que j’aimerais entendre autrement de quelqu’un plus compétent. Si tel est le cas, pourquoi est-il jugé raisonnable d’omettre l’indice?

Ma seule autre conjecture est que peut-être O (polylog (n)) est censé signifier “Asymptotique à une fonction polynomiale de log (n).” Mais ce n’est qu’une supposition: je n’en ai aucune preuve, et ce serait un abus de notation pour démarrer.

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

Abuser de la notation ou non, polylog (n) signifie “un polynôme dans log (n)”, tout comme “poly (n)” peut signifier “un polynôme dans n”. So O (polylog (n)) signifie “O ((log n) ^k ) pour certains k”. (Voir Wikipedia: Polylogarithmic , ou, pour le voir dans son contexte, blog du professeur Scott Aaronson: Mes taux de croissance préférés .)

Le fait est que, tout comme nous ne nous soucions pas souvent des facteurs constants, il est souvent commode d’ignorer les puissances des logarithmes. Parfois, les “facteurs de journalisation” sont complètement ignorés et vous pourriez voir “Õ (f (n))” – O avec un tilde au-dessus – ce qui signifie “O (f (n) polylog (f (n)))” , “O (f (n) (log f (n)) ^k ) pour quelques k”.

La façon dont il est utilisé dans cet article semble décrire quelque chose comme:

O (log ^ pn)

Polylog (n) est juste “polynomial dans le journal de n”. Wikipédia

Article de polylog Vous êtes deviner est assez proche.

Je suis sûr qu’ils ne signifient que l’axe réel positif entier: Re(n) = n

Wolfram vous propose une sélection dont la page polylogarithmique est la plus prometteuse.