算法速度慢

❶ 如何衡量一个算法的快慢

如何衡量一个算法的快慢
用具体的操作数来衡量

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

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

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

用函数来衡量

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

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