Polylogarithmique

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

[modifier] Définition

Une fonction polylogarithmique de n est polynomiale par rapport au logarithme de n. Elle a la forme suivante : a_k \log^k(n) + \cdots + a_1 \log(n) + a_0.

Attention, ne pas confondre avec les polylogarithmes.

[modifier] Propriétés

Une fonction polylogarithmique croît plus doucement que n'importe quel polynôme. Plus précisément, toutes les fonctions polylogarithmiques sont négligeables par rapport aux fonctions polynomiales au voisinage de l'infini :

\forall \epsilon \in \mathbb R^{+*} \quad P_l(x) = o(x^\epsilon)\,

[modifier] Applications

En informatique, les fonctions polylogarithmiques apparaissent dans les complexités de certains algorithmes (et en particulier des algorithmes parallèles, dans les classes de complexité parallèle).