多對數函數

的多對數函數（polylogarithmic function）是指n的對數的多項式

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

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

對於每個大於0的指數，也就是說，多對數函數成長的比每任何正指數的多項式函數都要慢。

計算複雜性理論所研究的資源中最常見的是時間（要通過多少步演算才能解決問題）和空間（在解決問題時需要多少存儲器）。其他資源亦可考慮，例如在并行計算中，需要多少并行處理器才能解決問題。

時間複雜度是指在計算機科學與工程領域完成一個演演算法所需要的時間，是衡量一個演演算法優劣的重要參數。時間複雜度越小，說明該演演算法效率越高，則該演演算法越有價值。

空間複雜度是指計算機科學領域完成一個演演算法所需要佔用的存儲空間，一般是輸入參數的函數。它是演演算法優劣的重要度量指針，一般來說，空間複雜度越小，演演算法越好。我們假設有一個圖靈機來解決某一類語言的某一問題，設有 個字（）屬於這個問題，把放入這個圖靈機的輸入端，這個圖靈機為解決此問題所需要的工作帶格子數總和稱為空間。

複雜度理論和可計算性理論不同，可計算性理論的重心在於問題能否解決，不管需要多少資源。而複雜性理論作為計算理論的分支，某種程度上被認為和演演算法理論是一種“矛”與“盾”的關係，即演演算法理論專註於設計有效的演演算法，而複雜性理論專註於理解為什麼對於某類問題，不存在有效的演演算法。

多項式（Polynomial）是代數學中的基礎概念，是由稱為未知數的變數和稱為係數的常數通過有限次加減法、乘法以及自然數冪次的乘方運算得到的代數表達式。多項式是整式的一種。未知數只有一個的多項式稱為一元多項式；例如就是一個一元多項式。未知數不止一個的多項式稱為多元多項式，例如就是一個三元多項式。

可以寫成只由一項構成的多項式也稱為單項式。如果一項中不含未知數，則稱之為常數項。

多項式在數學的很多分支中乃至許多自然科學以及工程學中都有重要作用。