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

Question

我在一些算法书籍中读到了有关算法运行时间的内容，它被表示为O(n)。例如，对于最佳情况，给定的代码将在O(n)的时间内运行，而对于最坏情况则是O(n³)。这是什么意思，如何计算自己代码的运行时间？它是否像线性时间一样，每个预定义库函数都有自己的运行时间，需要在调用之前记住？谢谢...

- user837598

---

可能是重复问题：https://dev59.com/enVD5IYBdhLWcg3wXaYd - River

Answer 1

《初学者指南：大O符号》可能是一个很好的起点：

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

同时，您也可以参考维基百科：

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

在stackoverflow上还有几个相关问题和好的回答：

什么是“大O符号”的简明英文解释？

以及

供8岁孩子理解的大O符号？

- amdn

Answer 2

这不应该在数学里吗？

如果您正在尝试使用冒泡排序数组进行排序，而该数组已经排序，则可以检查是否沿着数组移动了任何内容。如果没有，一切都好 - 我们完成了。

因此，对于最佳情况，您将具有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>n f（m）

实际上，您必须在维基百科上阅读关于O符号的内容。

- KAction

Answer 3

大O符号是一种渐进符号。渐进符号是数学中的一个概念，描述了函数在无限趋近于某个值时的行为。

定义算法运行时间的问题在于，你通常无法用毫秒来回答，因为它取决于机器；你也不能用时钟周期或操作计数来回答，因为那对特定数据太具体而不实用。

简单地说，渐进符号会舍弃函数中的所有常数因子。基本上，如果n足够大（假设一切都是正数），那么n²始终比b n大。更改常数因子a和b并不会改变这一点，它只会改变a n²比b n大的具体值，但并不会改变其发生的事实。因此，我们说O(n²)比O(n)大，并忘记那些我们可能无法知道的常数。

这很有用，因为当n变大时，问题通常会变得足够缓慢以至于我们真正关心。如果n足够小，则所需时间很短，从选择不同的算法中获得的收益也很小。当n变大时，选择不同的算法可能会产生巨大的差异。此外，在现实世界中发生的问题通常比我们可以轻松测试的问题要大得多 - 而且通常随着数据库积累更多数据而不断增长。

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

MIT OCW Introduction to Algorithms 课程非常适合这种情况。视频和其他材料可免费使用，而课程书（非免费）是最好的算法书之一。

- user180247