[理工] 關於pseudo-polynomial time st474ddr PTT批踢踢實業坊

[理工] 關於pseudo-polynomial time

作者: st474ddr (hikke) 2019-01-23 20:48:52

各位大大好
小弟有對於這個地方一直有疑問
看了一些文章看了一些視頻
有種似懂非懂的感覺
所以想請教各位大大
關於pseudo-polynomial time
以0-1背包舉例若重量為W
我明白logW才是input
但我不懂為何這裡要把input看成用bit去存
我們一般的polynomial time的算法為什麼都不用考慮?
就可能現在有個O(k*n)的algo
但我們考慮n 的input size
貌似這個algo就變成exponential了
這樣是合理的嗎?
感謝各位大大

作者: school4303 (某爬蟲類) 2019-01-23 21:02:00

k*n k^n ?

作者: fatezero5262 (白羽音人) 2019-01-23 21:12:00

https://goo.gl/dsdcLJ （1:31:25）台大ada課程

作者: FRAXIS (喔喔) 2019-01-23 21:55:00

#1N-azPo 之前的討論

作者: alen0303 (艾倫零參智商負三) 2019-01-23 21:59:00

一般的演算法其實也有考慮例如n個整數作sorting 一個整數用32bits存 input size就是32n 依然是O(n)的空間

作者: st474ddr (hikke) 2019-01-24 13:55:00

感謝各位大大我研究研究

作者: ekids1234 (∵:☆星痕╭☆) 2019-01-24 18:57:00

找不到該文章帶碼 Q

作者: FRAXIS (喔喔) 2019-01-24 20:33:00

#1N-azPo9 sorry

繼續閱讀

[理工] 106交大線代 11-gkarta0703133 [理工] 104交大演算法AAQ8 [理工] [核對]107成大土木結構組材料力學答案gl4rmp4 Re: [理工] 107中央資工數學對答案bmpss92196 [理工] 三題交大103硬體cvn21 [理工] 線代反矩陣求法magic83v [理工] 107 清大計系Youhao [理工] 106中山DSAAQ8 [理工] 關於Transitive closure的疑問jojoboy0115 [理工] 作業系統 deadlock avoidance題目susukila