如何衡量一个算法的快慢-轻识

数学算法俱乐部

日期： 2021年10月03日

正文共：2171字

来源：南方小智

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

用具体的操作数来衡量

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

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

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

用函数来衡量

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

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

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

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

‍‍用近似函数来衡量

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

我们从直观上来理解这种近似是合理的。首先，当数据规模n达到十万的时候，4n^

4 n 2 "> 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)其实是渐近等价的。