作者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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1548247735.A.C8F.html
1F：→ school4303: k*n k^n ? 01/23 21:02
3F：推 FRAXIS: #1N-azPo 之前的讨论 01/23 21:55
4F：推 alen0303: 一般的演算法其实也有考虑 例如n个整数作sorting 一个整 01/23 21:59
5F：→ alen0303: 数用32bits存 input size就是32n 依然是O(n)的空间 01/23 21:59
6F：→ st474ddr: 感谢各位大大 我研究研究 01/24 13:55
7F：推 ekids1234: 找不到该文章带码 Q 01/24 18:57