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

看板Grad-ProbAsk作者FRAXIS (喔喔)時間9年前 (2016/10/09 22:08)推噓4(4推 0噓 9→)

留言13則, 5人參與討論串2/3 (看更多)

※ 引述《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

10/09 22:35, , 1^F

10/09 22:35, 1^F

→

FRAXIS

10/09 22:43, , 2^F

10/09 22:43, 2^F

→

FRAXIS

10/09 22:45, , 3^F

10/09 22:45, 3^F