Polylogarithmic function とは

nにおける多項式関数は、nの対数の多項式であり、
a k ( log n ) k + + a 1 ( log n ) + a 0 . {\displaystyle a_{k}(\log n)^{k}+\cdots +a_{1}(\log n)+a_{0}.}
コンピュータサイエンスでは、いくつかのアルゴリズム(例えば、「ポリロゴナルオーダー」を有する)によって使用される時間またはメモリのオーダーとして、ポリロ関数が生じる。
n {\displaystyle n} のすべての多項式関数は、すべての指数ε> 0(この記号の意味では小文字表記を参照)に対して o ( n ε ) {\displaystyle o(n^{\varepsilon })} であり、つまり、ポリロガル関数は任意の正の指数よりもゆっくりと成長する。この観測はソフトO表記υ(n)の基礎となる。