[理工] 关于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