我在一些算法书籍中读到了有关算法运行时间的内容,它被表示为O(n)
。例如,对于最佳情况,给定的代码将在O(n)的时间内运行,而对于最坏情况则是O(n3)。这是什么意思,如何计算自己代码的运行时间?它是否像线性时间一样,每个预定义库函数都有自己的运行时间,需要在调用之前记住?谢谢...
《初学者指南:大O符号》可能是一个很好的起点:
http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
同时,您也可以参考维基百科:
http://en.wikipedia.org/wiki/Big_O_notation
在stackoverflow上还有几个相关问题和好的回答:
以及
这不应该在数学里吗?
如果您正在尝试使用冒泡排序数组进行排序,而该数组已经排序,则可以检查是否沿着数组移动了任何内容。如果没有,一切都好 - 我们完成了。
因此,对于最佳情况,您将具有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符号的内容。
大O符号是一种渐进符号。渐进符号是数学中的一个概念,描述了函数在无限趋近于某个值时的行为。
定义算法运行时间的问题在于,你通常无法用毫秒来回答,因为它取决于机器;你也不能用时钟周期或操作计数来回答,因为那对特定数据太具体而不实用。
简单地说,渐进符号会舍弃函数中的所有常数因子。基本上,如果n足够大(假设一切都是正数),那么n2始终比b n大。更改常数因子a和b并不会改变这一点,它只会改变a n2比b n大的具体值,但并不会改变其发生的事实。因此,我们说O(n2)比O(n)大,并忘记那些我们可能无法知道的常数。
这很有用,因为当n变大时,问题通常会变得足够缓慢以至于我们真正关心。如果n足够小,则所需时间很短,从选择不同的算法中获得的收益也很小。当n变大时,选择不同的算法可能会产生巨大的差异。此外,在现实世界中发生的问题通常比我们可以轻松测试的问题要大得多 - 而且通常随着数据库积累更多数据而不断增长。
这是一个有用的数学模型,它抽象出了足够尴尬的细节,以便找到有用的结果,但它并不是一个完美的系统。在现实世界中,我们不处理无限的问题,有很多时候问题足够小,以至于这些常数对于实际性能是相关的,有时你只需要用时钟计时。
MIT OCW Introduction to Algorithms 课程非常适合这种情况。视频和其他材料可免费使用,而课程书(非免费)是最好的算法书之一。