多对数函数

  提示：此条目页的主题不是多重对数函数。

$n$的多对数函数（polylogarithmic function）也称为幂对数，是指$n$的对数的多项式

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

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

在计算机科学中，多对数函数在一些演算法时间和空间复杂度的数量级中用到（多对数级，PolyL）。

此外，多对数函数的指数成长是准多项式成长，类似多项式成长，若时间复杂度以准多项式成长的演算法，称为准多项式时间，类似多项式时间。

所有多对数函数都符合以下的形式

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

对于每个大于0的指数$\varepsilon$。(有关上述符号的定义，可以参考大O符号#常用的函数阶)也就是说，多对数函数成长的比每任何正指数的多项式函数都要慢，有时会被当作小量在${\tilde {O}}$符号中忽略。

参考资料

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