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.
image illustrant les mathématiques
Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Consultez la liste des tâches à accomplir en page de discussion.

Une fonction polylogarithmique [1] 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]

  1. (en) Paul E. Black, « Polylogarithmic », Dictionary of Algorithms and Data Structures,‎ (lire en ligne)Voir et modifier les données sur Wikidata

Bibliographie[modifier | modifier le code]