作者:
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了
這樣是合理的嗎?
感謝各位大大