Polylogarithmique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Ne doit pas être confondu avec Polylogarithme.

Une fonction polylogarithmique[réf. souhaitée] 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.

Pour éviter les confusions avec les fonctions polylogarithmes, il vaut mieux parler de polynôme logarithmique[réf. souhaitée], par analogie avec les polynômes trigonométriques.

Propriétés[modifier | modifier le code]

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

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

Applications[modifier | modifier le code]

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).

Notes et références[modifier | modifier le code]