[理工] pseudo polynomial time

[NTUmaki (西木野真姬)]

版上兩篇文章看過了，但有些還是不懂、想確認

我目前理解是這樣：

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1599376538.A.02E.html
推 aarzbrv: 「我是取他有幾位數可以嗎？」的回答，就是您所理解到的
→ aarzbrv: 「所以取bit 數當他的size」。
推 aarzbrv: 會不會是因為還沒發明電腦的社會習慣用log 10，發明後用
→ aarzbrv: log 2，造成您的困惑呢？
→ NTUmaki: 不算困擾，只是想說關鍵應該是要把W的size量化成 隨著W這
→ NTUmaki: 個數字越大，他的size也要越大，所以取他有幾位也對吧
推 aarzbrv: 或是「取他有幾位(元)」，您是否認同在下多加一個字呢？
→ NTUmaki: 原本的我同意啊，只是我想說取幾位表達趨勢 也是exponent
→ NTUmaki: ial
推 aarzbrv: 您目前的主文與推文，在下如果沒會錯意的話，都同意；
→ aarzbrv: 希望在下的推文沒有誤導您的地方，抱歉！
→ NTUmaki: 不會不會 感謝回覆
推 FRAXIS: 主要是執行時間跟 W 有關，所以才要討論 bit。
→ FRAXIS: 像是 comparison-based 的 sorting 都是假設 comparison
→ FRAXIS: 是 O(1) 時間 與 bit 無關，所以就不用討論 bit。
→ FRAXIS: 但是你也可以定義 comparison 跟 bit 長度有關的計算模型
→ FRAXIS: 只是教科書上不太會這樣介紹..
好像也是...理論上數字越大要比越久
※ 編輯: NTUmaki (27.247.233.249 臺灣), 09/07/2020 20:14:19