作者NTUmaki (西木野真姬)
看板Grad-ProbAsk
標題[理工] pseudo polynomial time
時間Sun Sep 6 15:15:36 2020
版上兩篇文章看過了，但有些還是不懂、想確認
我目前理解是這樣：
0/1 knapsack problem 複雜度 O(nW)
n是物品數量（陣列有多少個‘’元素‘）
W就是一個數值（input 只會看到一個東西）
但數值跟物品數量都是人的定義，對電腦來說最後都是開了nW的二維陣列，算了nW格的東西。所以其實數值、數量對電腦程式來說沒差吧？
所以不太懂要取 m=lgW 然後說複雜度是O(n2^m) 的理由
目前我是這樣理解：
因為複雜度理論也是人定義的，所以當初我們要求的input 必須是一個可以數有多少個的東西，以此題來說，input就會真的出現n+1數字（n個價格、1個重量）
W我們沒辦法說他 size 是1，要找一個會隨著W變大而增長的東西當input size，所以取 bit 數當他的size
這邊再提一個疑問，如果我是取他有幾位數可以嗎？（取log 10為底，反正出來的是exponential）
-----
Sent from JPTT on my iPhone
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.247.233.249 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1599376538.A.02E.html
1F：推 aarzbrv: 「我是取他有幾位數可以嗎？」的回答，就是您所理解到的 09/06 15:59
2F：→ aarzbrv: 「所以取bit 數當他的size」。 09/06 16:00
3F：推 aarzbrv: 會不會是因為還沒發明電腦的社會習慣用log 10，發明後用 09/06 16:05
4F：→ aarzbrv: log 2，造成您的困惑呢？ 09/06 16:05
5F：→ NTUmaki: 不算困擾，只是想說關鍵應該是要把W的size量化成 隨著W這 09/06 16:11
6F：→ NTUmaki: 個數字越大，他的size也要越大，所以取他有幾位也對吧 09/06 16:11
7F：推 aarzbrv: 或是「取他有幾位(元)」，您是否認同在下多加一個字呢？ 09/06 16:21
8F：→ NTUmaki: 原本的我同意啊，只是我想說取幾位表達趨勢 也是exponent 09/06 16:22
9F：→ NTUmaki: ial 09/06 16:22
10F：推 aarzbrv: 您目前的主文與推文，在下如果沒會錯意的話，都同意； 09/06 16:27
11F：→ aarzbrv: 希望在下的推文沒有誤導您的地方，抱歉！ 09/06 16:28
12F：→ NTUmaki: 不會不會 感謝回覆 09/06 20:54
13F：推 FRAXIS: 主要是執行時間跟 W 有關，所以才要討論 bit。 09/06 22:20
14F：→ FRAXIS: 像是 comparison-based 的 sorting 都是假設 comparison 09/06 22:20
15F：→ FRAXIS: 是 O(1) 時間 與 bit 無關，所以就不用討論 bit。 09/06 22:20
16F：→ FRAXIS: 但是你也可以定義 comparison 跟 bit 長度有關的計算模型 09/06 22:21
17F：→ FRAXIS: 只是教科書上不太會這樣介紹.. 09/06 22:21
好像也是...理論上數字越大要比越久
※ 編輯: NTUmaki (27.247.233.249 臺灣), 09/07/2020 20:14:19