Re: [問題] 0/1背包問題的時間複雜度
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間13年前 (2011/10/25 09:58)推噓1(1推 0噓 0→)留言1則, 1人參與討論串2/4 (看更多)
※ 引述《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
推
10/25 14:53, , 1F
10/25 14:53, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 4 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12