如何衡量一个算法的快慢

来源: 数据与算法之美 作者: | 发布时间: 2016-04-29 15:35:49

本文是一篇算法时间复杂度的入门介绍。


作者:南方小智

来源:http://www.cnblogs.com/nfxz/p/5175359.html


本文是一篇算法时间复杂度的入门介绍。我将逐步引出为何要使用时间复杂度来衡量一个算法的快慢,并给出时间复杂度的表示符号,介绍了最好,最坏和平均时间复杂度。

用具体的操作数来衡量

当我们说衡量一个算法的快慢时,我们是希望找到一种方便的统一标准,使得对于同一个算法,我们的衡量标准不会受到一些不重要的因素影响而保持一致;对于不同的算法,我们能够比较它们的优劣并在实际的应用中进行选择。

一个自然的想法是测量这个算法运行所需要的时间,然后选择跑得快的算法。但是不同的机器运行的速度是不一样的,一个同样的算法在不同机器上测出来的时间可能非常不同。而且,每次想要知道一个算法的快慢如果都要在机器上通过计时来测量的话,是一件非常痛苦的事情,因为有些算法可能一次要跑上一天,一个月,甚至一个世纪。

一个有效的替代方法是通过计算一个算法用了多少次操作(或者说运算量)来衡量它运行的快慢,比如用了多少次加减法,乘除法,函数调用和赋值等操作。操作数越多,运行的所需要的时间就越多。这样的一种想法保证了我们对算法的衡量不会因为测试环境的变化而变化,也不用通过实际运行来测量,只需通过计算就能得到操作数的数量。

用函数来衡量

仅仅计算操作数的一个问题是:一个固定的算法,针对不同的输入规模,它所需要的操作数量是不一样的。比如一个排序的算法,排100个数字和排10000个数字相比,排10000个数字所需要的运算量会大很多。也就是,操作数是随输入规模变化的一个函数。


所以,我们假如输入规模是n,那么操作数就是f(n)。有时候,输入规模不只有一个,比如关于一个矩阵的算法需要的操作数,可能和矩阵的长和宽都有关系,这时候,f就变成了一个关于长和宽的二元函数,比如f(w,h)。这种扩展是合理的,但是为了讨论方便,我们先只考虑规模只是一个变量n的情况。


f可能形式会比较复杂。比如


那么三个函数到底谁才能代表这个算法的真正时间复杂度呢?为了满足统一的衡量标准,我们必须有一个选择方法。

用近似函数来衡量

为了解答这个问题,我们首先要认识到,在实践中,我们只关心算法在输入规模比较大的情况下的表现。因为现在的计算机每秒都能做上亿次运算,我们处理的实际问题也是规模比较大的。而当输入规模较大时,我们就可以通过只保留占最大比重的项,并忽略常数,来得到一个统一的近似函数表达式。对于上面的例子来说,近似函数就是:


我们从直观上来理解这种近似是合理的。首先,当数据规模
n达到十万的时候,4n^2是40n的一万倍,所以我们已经没有必要考虑40n了,我们舍弃小项,而只保留占最大比重的项。对于忽略常数,是因为,当我们比较两个不同的时间复杂度的时候,常数是无关紧要的:考虑两个时间复杂度n^2和100n。100是比1大很多的,但是当n达到十万的时候n^2是100n的一千倍,可见常数的影响是非常小的。或者说,常数不会随输入规模n的变化而变化,当输入规模越来越大的时候,常数的影响力就越来越小。

这种机智的取舍解决了很多细节问题,比如,不同的操作可能会耗时不同,就好像加法操作要快些,乘法要慢些,除法可能更慢,而内存的读写操作可能比逻辑操作更慢些。在一些要求非常精细的情况下,我们可能不得不仔细分开不同的操作,但是,在一般情况下,如果我们忽略常数造成的差异,我们可以把这些不同的操作看成是一个操作单元,也就是说,虽然乘法比加法慢了2倍,但2只是个常数,我们把这种差异忽略掉。


近似函数是渐近的

现在我们从另一个角度来理解这个近似函数。


n不断增大时,如果f(n)和g(n)的比值趋向于稳定(稳定等于一个不等于0的常数),我们就认为f(n)和g(n)其实是渐近等价的。


由此可见,我们选取的【函数四】是和前面的三个函数在变化趋势上是渐近的。总的来说,我们找到了一个统一的标准,两个程序员的编码风格所造成的差别不存在了。

表示符号

目前,我们找到了操作数关于输入规模的一个近似函数来表示算法运行的快慢。这个近似函数就表示了算法的时间复杂度,通常我们会说某个算法的复杂度是O(f(n))或者Θ(f(n))。下面就说明不同的表示符号代表的含义:


很多时候,我们都会使用O符号,因为我们一般只会证明一个算法复杂度的上界(最坏情况),如果这个上界达到我们的要求了,就不必计算下界了。


这里举一个例子,对于一个时间复杂度为n2的算法,我们可以说:



最坏,最好和平均时间复杂度


前面我们讨论了算法的操作数随输入规模变化,但是即使是相同规模的数据,也能造成操作数的差异。这个时候,如果我们对每种可能的输入都进行时间复杂度的计算的话,是非常麻烦且没有必要的。我们一般只考虑最坏,最好和平均情况下的时间复杂度:


最坏时间复杂度:在所有可能的输入中,操作数最多的输入的时间复杂度。
最好时间复杂度:在所有可能的输入中,操作数最少的输入的时间复杂度。
最坏时间复杂度:对所有可能的输入的操作数取均值得到的时间复杂度。


这种表示时间复杂度的方法也可以运用到空间复杂度的上,在这种复杂度的表示方法下,程序员们可以愉快地攀比谁的算法更优,而不需要考虑实际实现的差异和具体运行环境等细枝末节的东西。


长按二维码关注,回复“女朋友”


呵呵,关注这个号的人运气不会太差

公众号导航