O(1) 的小樂

   在計算復雜性里面，如果一個算法的時間復雜度是輸入數據的多項式表達，但卻是輸入長度的指數時間算法，那么稱其為偽多項式時間。

    如果一個NPC問題存在偽多項式時間算法，那么稱其為Weakly NP-Complete。否則，稱為Strongly NP-Complete.

   很明顯的一個例子是0-1背包問題，這一點經常容易引起別人的誤解。其實0-1背包問題是一個NPC問題，你可以簡單的把它規約到子集和問題，但是有人經常爭辯說0-1 kanpsack問題存在Polynomial Algorithm，那么問題就在這里，那個所謂的Polynomial Algorithm is Pseudo-Polynomial actually！

   一個經典0-1背包問題的DP解法的時間復雜度是O(nW)，W為背包容量，但是背包容量是否需要枚舉[min(…),\sum(…)]呢？所以問題就在這里了復雜度是O(n2^n)…

   還有一個問題就是素性檢測！這個當然也是NPC的了。。

    In the case of primality, it turns out there is a different algorithm for testing whether n is prime (discovered in 2002) which runs in time O(log⁶n).

如果仍然不是很清楚，那么需要熟悉一下NPC與P類問題區別，下面是一個不錯的表格。。。

  不過貌似在源blog中有一處錯誤。。。Linear Programming的確是P問題，但是解決這個P問題的simplex 算法卻不是Polynomial的，這個需要注意！