[理工] 關於pseudo-polynomial time

看板Grad-ProbAsk作者 (hikke)時間7年前 (2019/01/23 20:48), 編輯推噓5(5推 0噓 3→)
留言8則, 6人參與, 7年前最新討論串1/1
各位大大好 小弟有對於這個地方一直有疑問 看了一些文章 看了一些視頻 有種似懂非懂的感覺 所以想請教各位大大 關於pseudo-polynomial time 以0-1背包舉例 若重量為W 我明白logW才是input 但我不懂為何這裡要把input看成用bit去存 我們一般的polynomial time的算法為什麼都不用考慮? 就可能現在有個O(k*n)的algo 但我們考慮n 的input size 貌似這個algo就變成exponential了 這樣是合理的嗎? 感謝各位大大 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.123.58.239 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1548247735.A.C8F.html
→
01/23 21:02, 7年前 , 1F
k*n k^n ?
01/23 21:02, 1F
推
01/23 21:12, 7年前 , 2F
https://goo.gl/dsdcLJ （1:31:25）台大ada課程
01/23 21:12, 2F
推
01/23 21:55, 7年前 , 3F
#1N-azPo 之前的討論
01/23 21:55, 3F
推
01/23 21:59, 7年前 , 4F
一般的演算法其實也有考慮 例如n個整數作sorting 一個整
01/23 21:59, 4F
→
01/23 21:59, 7年前 , 5F
數用32bits存 input size就是32n 依然是O(n)的空間
01/23 21:59, 5F
→
01/24 13:55, 7年前 , 6F
感謝各位大大 我研究研究
01/24 13:55, 6F
推
01/24 18:57, 7年前 , 7F
找不到該文章帶碼 Q
01/24 18:57, 7F
推
01/24 20:33, 7年前 , 8F
#1N-azPo9 sorry
01/24 20:33, 8F
‣ 更多 st474ddr 的文章
文章代碼(AID): #1SI6AtoF (Grad-ProbAsk)