查看“︁多對數函數”︁的源代码

{{not|多重对数函数}}
<math>n</math>的'''多對數函數'''（'''polylogarithmic function'''）也稱為'''幂对数'''，是指<math>n</math>的[[對數]]的[[多項式]]<ref>{{cite web|url=http://xlinux.nist.gov/dads/HTML/polylogarith.html|title=polylogarithmic|last=Black|first=Paul E.|date=2004-12-17|publisher=U.S. National Institute of Standards and Technology|work=Dictionary of Algorithms and Data Structures|accessdate=2010-01-10}}</ref>

:<math>a_k \log^k(n) + \cdots + a_1 \log(n) + a_0</math>

其中的{{math|log{{sup|''k''}}''n''}}是表示{{math|(log ''n''){{sup|''k''}}}}。

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

此外，多對數函數的[[指數函數|指數成長]]是{{le|準多項式成長|Quasi-polynomial growth}}，類似多項式成長，若時間複雜度以準多項式成長的演算法，稱為{{le|準多項式時間|Quasi-polynomial time}}<ref>{{ComplexityZoo|Class QP: Quasipolynomial-Time|Q#qp}}</ref>，類似多項式時間。

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

:<math>P_\ell(x) = o(x^\varepsilon)</math>

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

== 參考資料 ==
{{reflist}}
* {{cite web|url=http://xlinux.nist.gov/dads/HTML/polylogarith.html|title=polylogarithmic|last=E. Black|first=Paul|date=2004-12-17|work=Dictionary of Algorithms and Data Structures|publisher=U.S. National Institute of Standards and Technology|accessdate=2010-01-10|archive-date=2011-04-12|archive-url=https://web.archive.org/web/20110412145214/http://xlinux.nist.gov/dads/HTML/polylogarith.html|dead-url=no}}

[[Category:数学分析]]
[[Category:多項式]]
[[Category:算法分析]]