Polilogaritmikus

A polylogarithmic funkciója az n egy polinomiális függvény , hogy a logaritmusát ITS változó . Ennek a következő formája van:

{\ displaystyle f (x) = a_ {k} \ log ^ {k} x + \ cdots + a_ {1} \ log x + a_ {0}}

A polilogaritmusfüggvényekkel való összetévesztés elkerülése érdekében jobb logaritmikus polinomról beszélni , a trigonometrikus polinomokkal analóg módon .

Tulajdonságok

A polilogaritmikus függvény lassabban növekszik, mint bármelyik polinom . Pontosabban, a végtelenség szomszédságában az összes polilogaritmikus funkció elhanyagolható minden szigorúan pozitív kitevőnél a teljesítményfüggvényekhez képest :

{\ displaystyle \ forall \ varepsilon \ in \ mathbb {R} _ {+} ^ {*} \ quad f (x) = o (x ^ {\ varepsilon})}

Alkalmazások

A számítástechnikában a polilogaritmikus függvények bizonyos algoritmusok (és különösen a párhuzamos algoritmusok, a párhuzamos komplexitás osztályaiban ) bonyolultságában jelennek meg .

Referencia

(in) Paul E. Black "Polylogarithmic" a Dictionary of Algoritmusok és adatszerkezetek (in) , NIST ,2004. december 17( online olvasás ).