: ┌────────────────────────────────────── : │ 實際上，這個問題最大的癥結是： : │ 明明輸入的是變數W，但是為什麼不能和以前一樣輸入n就用n估算，輸入a就用a估算 : │ W好好的沒事還要變成2^logW : │ 才能下去算複雜度... : └────────────────────────────────────── http://en.wikipedia.org/wiki/Pseudo-polynomial_time 在這頁有提到質數檢查的問題，我覺得就是一個好例子： 考慮一個數 N ，請問他是不是質數？ 我們可以給出一個簡單的演算法： for each integer i, 2 <= i <= sqrt(N) if N Mod i = 0 return false return true 這個演算法的複雜度是 O(N^0.5) 是多項式時間 可是，對這個問題來說，我們關心的並不是 N 變成兩倍的話， 運算量會多多少 (Ex: N ~= 10000 和 N ~= 20000) 我們所關心的是，從 N ~= 2^32 變成 N ~= 2^64 會差多少？ 我們所謂的 "不同大小的輸入" 指的應該是 N ~= 2^n 中的 n 而不是 N ， 當 n 成長時，函數的執行時間會有什麼變化？ 是 O(2^(n/2)) 或是說加法，在一般的討論下，加法應該是 O(1) ，可是， 如果討論加法本身，也就是說，算兩個 n bits 的數字的和要多久？ 如果今天 n' = 2n ，又要多久？那就不是 O(1) 了，而是 O(n) 。 回到 0/1 kp ，大部分我們遇到的 W 都不大，而且變動的大多是 n ， 如果，今天的題目是： 給兩個數 n, w ，代表的是， 有 n 個物品，重量 0<= W <= 2^w ... 的 0/1 KP 問題，那你應該可以想像， w = 10 和 w = 100 所花的時間會差非常非常多。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.49.204