Polilogaritmikus függvény

Az n polilogaritmikus függvénye egy n logaritmusa szerinti polinom.

$a_{k}\log ^{k}(n)+\cdots +a_{1}\log(n)+a_{0}.\,$

A számítástudományban a polilogaritmikus függvények egyes algoritmusok memóriahasználat szerinti rendjének leírásakor fordulnak elő (pl. „polilogaritmikus rendű algoritmus”).

Minden polilogaritmikus függvényre igaz, hogy

$P_{\ell }(x)=o(x^{\varepsilon })\,$

valamennyi ε > 0 kitevőre (a szimbólum jelentéséhez lásd: Kis ordó jelölés), tehát egy polilogaritmikus függvény bármely pozitív kitevőnél lassabban növekszik. Ez a megfigyelés az alapja a „soft” O jelölésnek.

Irodalom

• E. Black, Paul: polylogarithmic. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology, 2004. december 17. (Hozzáférés: 2010. január 10.)