转载

如何衡量一个算法的快慢

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

当我们需要衡量一个算法的快慢时，一个自然的想法是测量这个算法运行所需要的时间。但是不同的机器运行的速度是不一样的，一个同样的算法在不同机器上测出来的时间可能非常不同，像60年代的计算机和如今的计算机就完全没有可比性了。而且，每次想要知道一个算法的快慢如果都要在机器上通过计时来测量的话，是一件非常痛苦的事情，因为有些算法可能一次可能要跑上一天，一个月，甚至一个世纪。

一个有效的替代方法是通过考虑一个算法用了多少次操作来衡量它运行的快慢，操作数越多，运行的所需要的时间就越多。这样的一种想法保证了我们对算法的衡量不会因为测试环境的变化而变化。

但是计算操作数仍然不能解决一个问题，通常一个算法是针对不同的规模所需要的操作数是不一样的，比如一个排序的算法，排100个数字和排10000个数字相比，排10000个数字所需要的运算量会大很多。

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

引入这个操作数的函数这一概念，似乎世界都美好了。我们先来看看这个函数是长成什么样的。问题规模 /(n/) 通常是一个自然数，而且，从直觉来看，随着 /(n/) 的增大， /(f/) 也会跟着增大。当 /(n/) 趋于无穷大的时候， /(f/) 也是趋于无穷的，也就是说：

/(f/) 是一个关于自变量 /(n/) 的无上界递增函数。

/(f/) 的另一个特点是， /(f/) 可能很复杂。比如

/(f(n)=4n^2+40n+93/)

更要命的是，不同程序员对相同算法的实现可能完全不同，比如A喜欢写"x++;"，而B喜欢写"x=x+1;"，后者有两个操作符，前者只有一个，这样 /(f(n)/) 可能就变成了

/(f(n)=4n^2+40n+94/)

甚至变成了

/(f(n)=2*(4n^2+40n+93)/)

所谓成大事者不拘小节，且不说一个操作实际占用的时间是以纳秒计算的，即便是一秒和两秒的差别，我们其实也不会太在意的——说白了，我们不关心常数倍数的差别，我们关心的是某种数量级意义上的差别。这可能是我们讨论时间复杂度的时候最大的难点了，也就是说

时间复杂度忽略了操作数函数之间常数大小的差异。

常数不会随问题规模 /(n/) 的变化而变化，当问题规模相当大的时候，常数只是个细枝末节的问题，甚至连 /(n/) 在 /(n^2/) 面前也只是个细枝末节的问题。试想想，当数据规模 /(n/) 达到十万的时候， /(4n^2/) 是 /(40n/) 的一万倍，我们还有必要考虑 /(40n/) 吗？

我们希望把上面两个由于常数差别而造成不同的函数看成同一个。这个同一类函数的代表，其实就是我们说的时间复杂度了。从这个例子来说，我们把 /(f(n)=4n^2+40n+94/) 和 /(f(n)=2*(4n^2+40n+93)/) 都看成 /(n^2/) 。这样一来，两个程序员的编码风格所造成的差别就不存在了。

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

这种忽略常数的时间复杂度技巧通过【渐近函数的关系】严格地描述了出来，而这种技巧也同样地可以运用到空间复杂度的表示上。在这种复杂度的表示下，程序员们可以愉快地攀比谁的算法更优，而不要考虑实际实现的差异和具体运行环境等细枝末节的东西。

原文 http://www.cnblogs.com/nfxz/p/5175359.html

正文到此结束