fonction polylogarithmique

En mathématiques , une fonction polylogarithmique en n est un polynôme en logarithme de n ,

{\displaystyle a_{k}(\log n)^{k}+a_{k-1}(\log n)^{k-1}+\cdots +a_{1}(\log n)+a_{0}. <semantics><mrow><mstyle><msub><mi>un</mi><mrow><mi>k</mi></mrow></msub><mo>(</mo><mi>enregistrer</mi><mo>⁡</mo><mi>n</mi><msup><mo>)</mo><mrow><mi>k</mi></mrow></msup><mo>+</mo><msub><mi>un</mi><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>(</mo><mi>enregistrer</mi><mo>⁡</mo><mi>n</mi><msup><mo>)</mo><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mi>un</mi><mrow><mn>1</mn></mrow></msub><mo>(</mo><mi>enregistrer</mi><mo>⁡</mo><mi>n</mi><mo>)</mo><mo>+</mo><msub><mi>un</mi><mrow><mn>0</mn></mrow></msub><mo>.</mo></mstyle></mrow><annotation>{\displaystyle a_{k}(\log n)^{k}+a_{k-1}(\log n)^{k-1}+\cdots +a_{1}(\log n)+a_{0}.}</annotation></semantics></math></span><img src=

La notation log ^k n est souvent utilisée comme raccourci pour (log n ) ^k , analogue à sin ²θ pour (sin θ ) ² .

En informatique , les fonctions polylogarithmiques apparaissent comme l' ordre de temps de certaines opérations sur les structures de données . De plus, la fonction exponentielle d'une fonction polylogarithmique produit une fonction à croissance quasi-polynomiale , et les algorithmes ayant cette complexité temporelle sont dits s'exécuter en temps quasi-polynomial .

Toutes les fonctions polylogarithmiques de n sont de classe O( nε ⁾ pour tout exposant ε > 0 (pour la signification de ce symbole, voir la notation O(n ) ), c'est-à-dire qu'une fonction polylogarithmique croît plus lentement que n'importe quel exposant positif. Cette observation est à la base de la notation O ( n ) .