algorithm - 如何计算算法的运行时间？

Question

我在一些算法书籍中读到了算法运行时，它表示为，O(n). 例如，给定的代码在最佳情况下运行时间为 O(n)，最坏情况下运行时间为 O(n ³ )。这是什么意思以及如何为自己的代码计算它？是不是像线性时间一样，是不是每个预定义的库函数都有自己的运行时，在调用它之前应该牢记这一点？谢谢...

Answer 1

Big O Notation 初学者指南可能是一个不错的起点：

http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

也看看维基百科

http://en.wikipedia.org/wiki/Big_O_notation

stackoverflow上有几个相关的问题和好的答案

“Big O”符号的简单英文解释是什么？

和

八岁的Big-O？

Answer 2

big-O 符号是一种渐近符号。渐近符号是数学中的一个概念，它描述了函数“在极限内”的行为——当你接近无穷大时。

定义算法运行时间的问题在于，您通常无法以毫秒为单位给出答案，因为它取决于机器，并且您无法以时钟周期或操作计数的形式给出答案，因为那将是对特定数据过于具体而无用。

查看渐近符号的简单方法是它丢弃函数中的所有常数因子。基本上，如果 n 足够大（假设一切都是正数），则²将始终大于 bn。改变常数因子 a 和 b 不会改变这一点 - 它会改变 n 的特定值，其中²更大，但不会改变它的发生。所以我们说 O(n ² ) 比 O(n) 大，并且忘记那些我们可能无论如何都不知道的常数。

这很有用，因为 n 较大的问题通常是速度慢到我们真正关心的问题。如果 n 足够小，则所花费的时间很短，选择不同算法可获得的收益也很小。当 n 变大时，选择不同的算法会产生巨大的差异。此外，现实世界中发生的问题通常比我们可以轻松测试的问题大得多——而且它们通常会随着时间的推移而不断增长（例如，随着数据库积累更多数据）。

这是一个有用的数学模型，可以抽象出足够多难以处理的细节，从而可以找到有用的结果，但它不是一个完美的系统。我们不会处理现实世界中的无限问题，而且很多时候问题足够小，以至于这些常数与现实世界的性能相关，有时你只需要用时钟来计时。

MIT OCW Introduction to Algorithms课程非常适合这种事情。视频和其他材料是免费提供的，课程书（不是免费的）是最好的算法书籍之一。

Answer 3

这不应该是数学吗？

如果您尝试使用已经排序的冒泡排序数组进行排序，那么您可以检查这个移动数组是否检查了任何内容。如果没有，没关系——我们完成了。

比，在最好的情况下，您将有 O(n) 次比较（准确地说是 n-1），对于最坏的情况（数组反转），您将有 O(n^2) 次比较（n(n-1)/2 ，确切地说）。

更复杂的例子。让我们找到数组的最大元素。很明显，您总是会进行 n-1 次比较，但平均分配多少次？复杂的数学答案：H(n) -1。

通常，您的答案很容易获得最佳和最坏情况，但平均需要大量数学。

我建议您阅读 Knuth，第 1 卷。但谁不会呢？

而且，正式定义：

f(n)∈O(g(n)) 表示存在 n∈N：对于所有 m>nf(m)

事实上，你必须阅读关于 wiki 的 O-notation。