多對數函數

Template:Not $n$的多對數函數（polylogarithmic function）也稱為幂对数，是指$n$的對數的多項式

$a_k{\log }^k(n)+\cdots +a_1\log (n)+a_0$

其中的Template:Math是表示Template:Math。

在計算機科學中，多對數函數在一些演算法時間和空間複雜度的數量級中用到（多對數級，PolyL）。

此外，多對數函數的指數成長是Template:Le，類似多項式成長，若時間複雜度以準多項式成長的演算法，稱為Template:Le，類似多項式時間。

所有多對數函數都符合以下的形式

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

對於每個大於0的指數$\epsilon$。(有關上述符號的定義，可以參考大O符号#常用的函数阶)也就是說，多對數函數成長的比每任何正指數的多項式函數都要慢，有时会被当作小量在$\tilde{O}$符号中忽略。

參考資料

• Template:Cite web