多對數函數

$n$ 的多對數函數（polylogarithmic function）也稱為幂对数，是指 $n$ 的對數的多項式^[1]

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

其中的 $log k n$ 是表示 $(log n) k$ 。

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

此外，多對數函數的指數成長是準多項式成長（英语：Quasi-polynomial growth），類似多項式成長，若時間複雜度以準多項式成長的演算法，稱為準多項式時間（英语：Quasi-polynomial time）^[2]，類似多項式時間。

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

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

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

參考資料

^ Black, Paul E. polylogarithmic. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 2004-12-17 [2010-01-10].
^ Complexity Zoo: Class QP: Quasipolynomial-Time

E. Black, Paul. polylogarithmic. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. 2004-12-17 [2010-01-10]. （原始内容存档于2011-04-12）.