多对数函数

$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）.