Re: [理工] 演算法 0-1knapscak觀念疑問

[FRAXIS (喔喔)]

※ 引述《shortid (我是短哀低)》之銘言：
: 大家好
: 這裡有一個觀念想要請教各位版友
: 書本上說0-1背包問題的複雜度是O(nW)=O(n2^m)
: m=lg W
: 這部分的解釋真的看不太懂，希望可以請教各位
: 我的理解是因為W其實僅需lg W bits即可，而卻需要處理W時間，所以相當於輸入m，卻花了2^m等級的時間
: 然而如果是這樣我覺得不懂的是那為什麼其他的問題沒有這個狀況呢？
: 其他問題我input n不也是只需要lg n bits就可以存了嗎？那為什麼其他問題不會有這個結論？
: 我猜我是對這個這個理解有誤，希望版友可以解惑，謝謝！！

要了解這問題，你要知道電腦是怎麼接受輸入的，以 knapsack 問題來說，
輸入有 n 個物品，第 i 個物品有重量 wi 和價值 vi 。
除此之外還有一個重量限制 W ，那在電腦之中需要多少 bit 來表示這些輸入？

假設輸入是下面的形式（當然也可能有其他形式，只是應該不會影響結果）
n,(w1,v1),(w2,v2), ...,(wn,vn),W

要表示 W 的值， W 至少要使用 m = lg W bits 。又因為時間複雜度是 O(nW)，
所以時間複雜度可以表示成O(n2^m)。

這情況常常出現在輸入是一個數值的情況。
另一個常見的例子是 factorization : 給定一個正整數 N > 1 ，把 N 作因式分解。
暴力法就是從 i = 2 ~ sqrt N 一個一個去試除來作因式分解。
時間複雜度是 O(sqrt(N)) ，但是基於相同的原因，這方法不是多項式時間的。
至今，除了量子電腦之外，還沒有多項式時間的方法來作因式分解。


那為什麼其他問題沒有這情況？
令除了 W 之外的輸入長度為 N bits 。

時間複雜度是要討論 worst case ，輸入當然可以使用 N bits 來只表示
一個物品，也就是 w1 或是 v1 特別的長。但是這樣並不會是 worst case ，
因為輸入的物件變少了，問題就簡單了。

所以 worst case 情況是用 N bits 表示越多物品越好。
因為每一個物品至少也要 O(1) bits 來表示，物品個數 n 就會是 O(N) 了。
此時輸入長度 N 也會是 O(n) 。
所以在這個時候就不用考慮物品輸入的長度，單純考慮個數就可以了，因為
O(NW) 和 O(nW) 是一樣的意思。

同理，排序問題也只需要考慮輸入的個數，而不是輸入的長度，因為個數和
長度是等價的。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 24.23.200.172
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1476022105.A.C89.html
推 a19930301: 抱歉，我聽不太懂W 至少要使用 m = lg W bits這個意思
→ FRAXIS: 二進位表示法 你要表示 1024 會需要1 + lg 1024 = 11 bits
→ FRAXIS: 所以如果 W 是 1024 ， m 就是 11
推 aa06697: 不太能理解O(1)那邊qq 輸入n=10個物品給電腦 10不是也是
→ aa06697: 一個「數值」嗎？
→ aa06697: 還是不會傳n進去 而是傳n個物品？這樣我好像就能理解原po
→ aa06697: 的說法 但一般寫程式在已知size狀況下多半會把他當參數傳
→ aa06697: 進去吧？！
推 kyuudonut: 樓上: 即使把n當參數傳進去 他還是得吃n筆資料啊!
→ kyuudonut: 抱歉我看錯ㄌ 原來你是指文章裡的N orz
→ FRAXIS: 是兩個都傳.. 但是要表示 n 所需要的位元數只有 lg n
→ FRAXIS: n 個物件至少要有 O(n) bits ，所以只要看這部份就好了..
推 shortid: 謝謝大大！！！！！