[理工] pseudo polynomial time

看板Grad-ProbAsk作者 (西木野真姬)時間5年前 (2020/09/06 15:15), 5年前編輯推噓5(5推 0噓 12→)
留言17則, 3人參與, 5年前最新討論串1/1
版上兩篇文章看過了，但有些還是不懂、想確認 我目前理解是這樣： 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
推
09/06 15:59, 5年前 , 1F
「我是取他有幾位數可以嗎？」的回答，就是您所理解到的
09/06 15:59, 1F
→
09/06 16:00, 5年前 , 2F
「所以取bit 數當他的size」。
09/06 16:00, 2F
推
09/06 16:05, 5年前 , 3F
會不會是因為還沒發明電腦的社會習慣用log 10，發明後用
09/06 16:05, 3F
→
09/06 16:05, 5年前 , 4F
log 2，造成您的困惑呢？
09/06 16:05, 4F
→
09/06 16:11, 5年前 , 5F
不算困擾，只是想說關鍵應該是要把W的size量化成 隨著W這
09/06 16:11, 5F
→
09/06 16:11, 5年前 , 6F
個數字越大，他的size也要越大，所以取他有幾位也對吧
09/06 16:11, 6F
推
09/06 16:21, 5年前 , 7F
或是「取他有幾位(元)」，您是否認同在下多加一個字呢？
09/06 16:21, 7F
→
09/06 16:22, 5年前 , 8F
原本的我同意啊，只是我想說取幾位表達趨勢 也是exponent
09/06 16:22, 8F
→
09/06 16:22, 5年前 , 9F
ial
09/06 16:22, 9F
推
09/06 16:27, 5年前 , 10F
您目前的主文與推文，在下如果沒會錯意的話，都同意；
09/06 16:27, 10F
→
09/06 16:28, 5年前 , 11F
希望在下的推文沒有誤導您的地方，抱歉！
09/06 16:28, 11F
→
09/06 20:54, 5年前 , 12F
不會不會 感謝回覆
09/06 20:54, 12F
推
09/06 22:20, 5年前 , 13F
主要是執行時間跟 W 有關，所以才要討論 bit。
09/06 22:20, 13F
→
09/06 22:20, 5年前 , 14F
像是 comparison-based 的 sorting 都是假設 comparison
09/06 22:20, 14F
→
09/06 22:20, 5年前 , 15F
是 O(1) 時間 與 bit 無關，所以就不用討論 bit。
09/06 22:20, 15F
→
09/06 22:21, 5年前 , 16F
但是你也可以定義 comparison 跟 bit 長度有關的計算模型
09/06 22:21, 16F
→
09/06 22:21, 5年前 , 17F
只是教科書上不太會這樣介紹..
09/06 22:21, 17F
好像也是...理論上數字越大要比越久 ※ 編輯: NTUmaki (27.247.233.249 臺灣), 09/07/2020 20:14:19
‣ 更多 NTUmaki 的文章
文章代碼(AID): #1VL8oQ0k (Grad-ProbAsk)