如果你看到这则信息,这表示下载可汗学院的外部资源时遇到困难.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

主要内容

渐近符号

到现在为止,我们通过计算可能需要的最大猜测次数,分析了线性搜索和二分搜索。但是我们真正想要知道的是这些算法需要 多久 。我们感兴趣的是 时间 而不仅是猜测次数。线性搜索和二分搜索的运行时间包括进行猜测并验证猜测的时间 ,但又不仅如此。
算法运行时间依赖于计算机花费多久时间去执行算法的代码—这取决于电脑的运行速度,以及采用的编程语言和编译器等因素。
让我们更仔细地思考算法的运行时间。我们能把两种思路结合起来。首先,考虑输入的规模,我们需要确定算法需要运行多久。这个思路很直观,不是吗?我们已经看到,线性和二分搜索中的最大猜测次数随数组长度增加而增加。或者想想GPS,如果他只知道州内的高速公路系统,而不知道小路,他就该更快的找到路线,对吧?所以我们把算法的运行时间看作一个于 输入规模相关的函数
第二个思路是我们必须关注函数运行时间随输入大小增长的速度。我们称之为运行时间的增长率。为了保持简洁,我们需要简化函数,提取出最重要的部分,把不那么重要的事情放到一边。例如,假设有一个算法,它的输入规模为 n,执行 6n2+100n+300 条机器指令。 当 n 变得足够大的时候,比如20,6n2 这一项比其他项,100n+300更大,这张图描述了6n2100n+300 的值随 n 从0到100变化而变化的情况:
我们会说算法的运行时间的增长为n2, 去掉了系数6和剩余项 100n+300。我们用什么系数并不重要;只要运行时间是an2+bn+c, 对于某些数字 a>0, b, 和 c, 总会存在 n ,使 an2 总是大于 bn+c,并且这一差额会随 n 增加而增加。 比如,以下的图表描述了0.6n21000n+3000 的值,我们将n2的系数减少到十分之一,将其他两项的系数增加到10倍:
n增长的时候, 0.6n21000n+3000 增长更快, 但不论常量如何,这里始终存在一个交汇点。
通过去掉不重要的项以及常量系数,我们可以专注于算法的运行时间的重要部分—增长率—而不用陷入把我们搞晕的具体细节。当我们去掉常量系数和不重要的项时,我们会使用渐进符号。我们将会看到三种形式:大 Θ 符号,大 O 符号,和大 Ω 符号。
本内容是 达特茅斯计算机科学 系的教授 Thomas CormenDevin Balkcom 以及可汗学院计算机课程团队合作完成。内容使用获得许可 CC-BY-NC-SA

想加入讨论吗?

尚无帖子。
你会英语吗?单击此处查看更多可汗学院英文版的讨论.