作者st474ddr (hikke)
看板Grad-ProbAsk
標題[理工] 關於pseudo-polynomial time
時間Wed Jan 23 20:48:52 2019
各位大大好
小弟有對於這個地方一直有疑問
看了一些文章 看了一些視頻
有種似懂非懂的感覺
所以想請教各位大大
關於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
→ school4303: k*n k^n ? 01/23 21:02
推 FRAXIS: #1N-azPo 之前的討論 01/23 21:55
推 alen0303: 一般的演算法其實也有考慮 例如n個整數作sorting 一個整 01/23 21:59
→ alen0303: 數用32bits存 input size就是32n 依然是O(n)的空間 01/23 21:59
→ st474ddr: 感謝各位大大 我研究研究 01/24 13:55
推 ekids1234: 找不到該文章帶碼 Q 01/24 18:57