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

• Sablon:Cite web