推 i78524:謝謝您！幫助真的很大！ 10/25 14:53
※ 引述《i78524 (Shulei)》之銘言：
: 儘管背包問題的時間複雜度為O(nW)，但它仍然是一個NP完全問題。這是因為W同問題的輸
: 入大小並不成線性關係。原因在於問題的輸入大小僅僅取決於表達輸入所需的比特數。事
: 實上，log W，即表達W所需的比特數，同問題的輸入長度成線性關係。
我對時間複雜度理論也不熟
以下是我看了維基百科之後的想法
時間複雜度通常有兩種input size
(1) 數值的大小（bit數量）
(2) 數字的數量（其實可以改為(1)的表示法，因為加減乘除都是多項式時間）
bubble sort的時間複雜度
用(2)的表示法是O(n^2)
一個數值有m個bit
兩個數字比大小是O(m)
用(1)的表示法是O(n^2 * m)
以m的角度來看是多項式時間
0/1 knapsack的時間複雜度
用(2)+(1)的表示法是O(nw)
一個數值有m個bit
用(1)的表示法是O(n * 2^m)
以m的角度來看是指數時間
不知道這樣想法正不正確？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.126.38