當一個算法的最壞時間複雜度是依據輸入的數量級的時候，我們就稱算法的時間複雜偶是偽多項式時間（給一個wiki上的解釋可能更好理解 若一個數值算法的時間複雜度可以表示為輸入數值規模N的多項式，但其運行時間與輸入數值規模N的二進制位數呈指數增長關係，則稱其時間複雜度為偽多項式時間。這是由於，N的值是N的位數的冪，故該算法的時間複雜度實際上應視為輸入數值N的位數的冪from wiki。
基本介紹
- 中文名：偽多項式時間
- 外文名：Pseudo polynomial time
例子,偽多項式和NP完全問題,推廣到非數字問題,複雜度,
例子
例如：統計一個數組中所有正數的出現頻率。算法是先找到最大的數max，然後從1到max遍歷沒一個數，找到這個數在數組中的出現頻率。這個算法需要的時間是取決於這個數組中最大的數的大小，所以說這個算法是偽多項式時間。換句話說，一個算法的時間複雜度只是根據輸入元素的多少的話，我們認為這個算法是多項式時間算法。
偽多項式和NP完全問題
有一些NP問題是有偽多項式時間的解法的，例如：0-1背包問題的動態規劃解法，子集和的問題（找出數組裡子集的和等於某個值的問題）， 切分問題。這都是偽多項式時間。如果一個NP完全問題有偽多項式時間的解法，那么我們稱這種問題叫弱NP完全問題。
推廣到非數字問題
雖然偽多項式時間的概念幾乎只用於數值問題，但概念可以推廣：如果m（n）不大於問題大小n的多項式函式，則函式m是偽多項式，並且是附加屬性 輸入，k（n）。 （據推測，k被選擇為與問題相關的東西。）這使得數值多項式問題成為一種特殊情況，將k作為輸入的數值。
數字的值與其長度之間的區別是編碼之一：如果數字輸入始終以一元編碼，則偽多項式將與多項式重合。
複雜度
如果一個算法的傳統時間複雜度是多項式時間的，而標準時間複雜度不是多項式時間的，則我們稱這個算法是偽多項式時間的。
想要理解“偽多項式時間”，我們需要先給出“多項式時間”的一個清楚的定義。
對於“多項式時間”，我們的直觀概念是時間複雜度
,其中k是一常數。比如，選擇排序的時間複雜度是
，是多項式時間；暴力解決TSP問題的時間複雜度是，不是多項式時間。我們稱這種時間複雜度為“傳統時間複雜度”。
