作者perturb (背後有老板)
看板Math
标题Re: [其他] 看不懂题目要问的意思
时间Thu Feb 24 10:11:03 2011
O(n^2)和O(2n)问题复杂度的感性认识
其实就是时间增加了K倍之後
对於线性的O(2n)，求解规模也可以增加到K倍
而对於O(n^2)，求解规模只能增加到K^{1/2}倍
另外一个就是说K很大时
对於复杂度的衡量来说n上头的指数重要而前头的系数不重要
以下N用1替换就好
※ 引述《kyoiori (瞎了)》之铭言：
: 请对於下表中各函数f(n)及各时间t，决定在时间内可解决的最大数量n。
: 假设各演算法需要f(n)毫秒时间解决问题。
: 然後列了一个表格
: 1秒 1分 1小时 1日
: n^2 N ~8N 60N ~300N
: 2n N/2 30N 1800N 12*3600N
: 这题我想了一段时间真的不太晓得题目要问什麽
: 是否有版友能提示方向
: 谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 162.105.195.208
1F：推 kyoiori :感谢！ 02/24 17:17