问该算法的时间复杂度是多少？
EN

Stack Overflow用户

提问于 2014-02-06 06:19:00

回答 1查看 34关注 0票数 1

问题大小=100万

算法运行时间= N^2

每秒操作数= 10^9

我的算法书中的表格说它需要“几个小时”才能完成，但根据信息，我认为它将需要“分钟”。我的思维过程是...

(100万)^2 /( 10^9 )= 1000秒，不到一个小时。我哪里错了？谢谢。

发布于 2014-02-06 07:15:27

您提到的表很可能只是一个粗略的估计，以秒/小时/天/年为粒度。这样一个表的目的可能只是传达一种关于O(N^2)实际含义的感觉:用O(N^2)算法对包含10000000个条目的电话簿进行排序？这不是个好主意。

这是肯定的事实，渐近运行时间，当它是以O-记法，省略了任何恒定因素。因此，O( N^2 )中的算法可能实际执行例如7.2 *N^2操作来完成其任务。你有7200秒，也就是2小时。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/21589789

复制

相似问题

问该算法的时间复杂度是多少？EN