僞多項式複雜度

上篇的标記算法中，談到這個O(K)的算法是一個指數級複雜度的算法，其實對那道題目本身來說，K是固定的，既然不是輸入，那也無所謂複雜度，之是以有O(K)這種說法，是把K當做一種輸入了，這是看待輸入的角度問題，倒不用深究。考慮一個更簡化的算法（python代碼，設輸入n是正整數）：  

def f(n): 
    i = 0 
    while i < n: 
        i += 1 
           

這個算法在任意整數輸入下都傳回None，我們關注的重點是它的時間複雜度，根據python的相關機制，指派操作是一個指針修改，可以認為是常數時間完成，于是這個算法執行了n次比較運算和加一運算  

之是以用python舉例，因為python的整數和C的整數類型不同，是不限制位數的（由于記憶體有限，實際還是有限制的，但也足夠大了），也就是說，不能将整數的所有運算都看做是常數時間的，因為數字可能非常大，在内部是用一個數組來存儲。最簡單的例子，兩個數字a和b相加，需要做的工作和它倆的長度有關，是以加法時間複雜度是和lga，lgb線性相關  

不過在這個例子中，我們可以證明比較和加一運算都是平均常數時間的，如果兩個大數比較，先看長度，長的那個顯然大，如果一樣長，則從前往後用類似strcmp的算法，根據前面某篇的讨論，strcmp的平均時間複雜度是O(1)；另一方面，雖然上面說加法跟數字的位數線性相關，但若是加一運算，隻有在産生連續進位的時候運算時間才和長度有關，而連續加一操作平均每次是常數時間（參考算法導論的平攤分析一章）  

于是我們就可以說，上面這個算法的複雜度是Θ(n)，這個結論沒有錯，但這個算法是一個指數級複雜度，原因在于，輸入規模并不是和n線性相關的，對于一個算法的輸入規模，有一個明确簡單的定義，就是輸入的長度  

由此，可以把輸入分為兩種，資料輸入和數值輸入，假設使用2進制作為表示形式，則對于一個數值N來說，它的輸入規模是lgN，當然，如果使用base大于2的進制，輸入長度會短，但從漸進意義上來說是一樣的，因為當x和y都大于1的時候，Θ(log(N,x))=Θ(log(N,y))，是以用二進制就能說明問題了。時間複雜度為Θ(T(N))，可以認為當輸入規模變為原來的k倍時，算法運作時間大約會增長到原來的T(k)倍這個級别，是以就上面這個算法來說，如果輸入規模增長到原來的k倍，那輸入的數值n會變成原來的k次方，是以，由于n是數值輸入，Θ(n)改寫成以輸入規模N的表示，就是Θ(2^N)，是一個指數級别複雜度  

對于資料輸入，就比較好了解了，如果不考慮每個資料本身的數值長度（有時候還是要考慮），則資料輸入的規模就是其數量  

假如一個算法有數值輸入，且其時間複雜度可以表示為輸入數值（不是輸入規模）的多項式，則根據上面的讨論，實際應該是一個指數時間的算法，但這種情況畢竟和資料輸入規模的指數級複雜度有些不同，一般來說，直覺上也習慣用輸入數值來表示複雜度，對于這種看上去像是多項式（數值的多項式）而實際代表算法是指數級（輸入規模作為指數）的複雜度，稱其為僞多項式複雜度  

很多算法具有僞多項式複雜度，例如，采用從2開始試除的方式判定一個整數N是否是素數，需要做N^(1/2)次除法，而每次除法的時間跟lgN有關，乍一看這個多項式也不高，但由于N會随着輸入規模很快增長，仍然是一個指數時間的算法，用它判定素數是很低效的  

P.S.聽說已經有了多項式時間判定素數的算法，時間複雜度是O((lgN)^6)到O((lgN)^12)，當然這裡由于N會随着輸入規模的線性增長而指數級增長，是以不妨設輸入規模M=lgN，就容易了解了  

利用動态規劃，0-1背包問題可以有一個O(NW)的算法，由于W是數值輸入，是以這個算法是僞多項式時間的。事實上，通過計算理論中的方法，可以證明0-1背包問題是一個NPC問題，如果不了解僞多項式，就很難了解為何它有一個O(NW)的算法，卻是NPC的  

存在僞多項式時間複雜度算法的NPC問題，一般稱為弱NPC問題，反之則是強NPC問題，弱NPC問題似乎更“接近”P，在相關問題的研究中經常引起人們更大的興趣