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^{\epsilon })$

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