背包問題眾所皆知是NP complete,
但它有DP的解法, 若有 N 個item, 背包能裝的max weight是W,
需要O(N*W)的時間

看起來很像polynomial time,
使我一度搞不清楚input size的定義

今天去找老師確認觀念,
其實很簡單, 像是求質數的笨方法需要N^(0.5)的時間 (N是數字的值),
它不是polynomial time, 而是exponential time,
因為input size是log(N), 所以 N^(0.5) = (2^log(N))^(0.5)

同樣地, O(N*W), W是個值, 應該表示成2^log(W), log(W)是W的size,
所以即使是DP解仍是exponential time, 非polynomial

理論上這樣說沒錯啦, 但algorithm或是解題時又是另一回事了,
所以和別人討論complexity時要分清楚是用什麼角度分析 :p

個人的感覺是,
當我在想algo時, 可能寫出個O(k*n), 並且表示這個做法快多了,
如果有個傢伙跳出來說,
"不不不, 你那個n要用size去算, 其實是exponential的"

我會覺得這樣的討論很蠢, 很沒意思,

但在討論NP, formal language, 計算理論(*1)時,
對方這麼說的話, 就很有道理了

PS

*1
今天sctsai宣傳了一下計算理論, 聽起來很有趣的樣子,
在更高深莫測的地方做更抽象的思考, 嗯, 有什麼用是另一回事

但他建議課不涼的人別去修, 不然會爆的