5分钟足矣——算法的时间复杂度

背景

算法（Algorithm）是解决特定问题的一组方法，比如比较典型的排序算法。

算法的时间复杂度是用来度量算法的执行时间的指标，一个算法的好坏，执行时间是关键因素。

给定10000个大小不一的数字，需要程序从小到大排好序。完成这个任务，会有n多种不同的算法。

虽然结果相同，但不同算法的执行时间会有很大区别。

影响程序执行时间的因素，有下面几个：

• 算法本身
• 问题规模，比如计算100个数字的排序或100000个数字的排序，执行时间肯定不一样
• 硬件条件，cpu运算能力大小
• 代码条件，不同的编程语言的执行效率有区别

这四个因素中，前两个是主观因素，后两个是客观因素。

我们研究算法问题，往往是在给定客观因素的前提下，只考虑算法和规模的不同，对解决一个特定问题所需要的执行时间，有何不同。

好了，总结一句话就是，影响执行时间的两个因素就是算法和规模。

表示成函数关系就是：T(n)=O(f(n))，意思是，如果一个问题的规模是n，解决这一问题的某一个算法所需要的时间为T(n)，T(n)称为这一算法的“时间复杂度”。

以上就是大O表示法，用于表达算法的时间复杂度。

算法的操作数量

在确定了问题规模n以后，好的算法和差的算法有啥区别呢？

比如排序算法，同样是给10000个数字排序，A算法需要执行10000次排序能到最后的结果，而B算法只需要执行5000次就可以得到同样的结果，因此，B算法是不是更好的呢？

我们可以得出一个结论，算法的执行时间的大小，取决于操作数量的多少。

那么判断不同算法执行时间的问题，就转化成比较操作数量的问题。

时间复杂度

对于给定的问题规模n，不同算法的操作数量可以表示成n的函数。

比如：有的算法f1(n) = a，代表操作数量与n无关，恒等于一个值。

有的算法f2(n)=n，代表操作数量与n线性相关，比如与n相等。

有的算法f3(n)=n^2，代表操作数量与n指数相关，也就是随着n的增长，操作数量增长更快。

如下图：

上面三个算法哪个的时间复杂度更低呢，答案是显而易见的，比较上面三个曲线，当n足够大的时候的函数值即可，f1<f2<f3。

当然，在n比较小的时候，也许有其它可能，但这种极端情况不考虑。再加上其它客观因素的影响，一般评价算法的时间复杂度的时候，都会把n设置的足够大，比如十万、百万级别，才有意义。

在算法上，一般用n的最高阶代表这个算法的时间复杂度，因为在数学上，当n足够大时，低于最高阶的项都可以忽略不计。

比如上面三个算法的时间复杂度分别是:常数阶O(1)、线性阶O(n)、平方阶O(n^2)。

当然除此之外，还有对数阶O(logn)、线性对数阶O(nlogn)等等，原理类似。

总结

我们的推导过程是：

算法的时间复杂度取决于算法和规模n 不同算法的算法的执行时间取决于操作数量 而操作数量与规模n存在函数关系 算法的事件复杂度，取决于规模n的最高阶数

好的，时间复杂度讲清楚了，下次聊聊算法的空间复杂度。

注：

• 大道至简，坚信复杂的理论背后，都有一个简单的道理。
• 5分钟原则，知识碎片化，一篇小文能讲清一个事儿就满足了。