一文读懂时间复杂度

算法就是为了提高代码运行效率，衡量算法的性能有两个考量指标：

时间复杂度与空间复杂度，它会伴随你学习算法的始终。

今天先谈一谈时间复杂度，在学习时间复杂度之前，我建议你先思考为什么需要复杂度。

插一句，很多时候，了解一个知识为什么出现可能比知识本身还要重要，无论是算法学习还是整个计算机领域。

为什么需要分析复杂度

时间复杂度，不就是衡量代码的执行时长吗，我直接写好代码在机子上一跑不就知道了吗。

为什么要多此一举？只是为了更学术、更官方吗？

测试环境

同样的代码在不同的机器上执行速度不同，每台机器的配置高低会影响代码执行效率。甚至，在你的电脑上，A算法比B算法快，到了我的电脑上反而B算法更快。
数据规模

拿排序来说，对十个数据排序和对十万个数据排序当然执行时间不一样，数据规模太小则无法反应算法的性能。举个栗子，快速排序是优于选择排序的，但数据规模较小时，快排却没选排快。

那怎么办，难道每次介绍算法前都要写上：在XXX配置和XXX数据规模下，算法执行效率XXX。

那太麻烦了，为此引入一个不需要考虑以上差异的衡量算法性能的标准，就是今天所说的时间复杂度分析。

大 O 表示法

知道了时间复杂度的由来，再谈谈该怎么表示。算法的执行效率就是看算法的执行时间，那怎么在不执行代码的情况下知道执行时间呢？

最朴素的办法就是看代码执行了多少行呗，举个栗子，看一段简单代码：

int func(int n) {
  int sum = 0;
  for(int i = 1; i <= n; ++i) {
    sum = 0;
  	for(int j = 1; j <= n; ++j) {
      sum = i + j;
    }
  }
  return sum;
}

作为粗略估计，假设每行代码的执行时间一样，记为TIME。现在来计算这段代码执行时间是多少，第2行执行一次只需要一个TIME，第3、4行外层循环执行了n次，所以需要2n个TIME，而第5、6行内层循环执行了n^{2次，所以需要2n}2个TIME。

所以，这段代码的执行时间T(n) = (2n^2 + 2n + 1) * TIME。

TIME可以认为是一个常量，代表一行代码的平均执行时间。然后可以发现，执行时间与代码执行次数n成正比。

为了方便表示，我们把代码执行次数记为f(n)，那么上面那个例子的代码执行次数f(n) = 2n^2 + 2n + 1。

所以T(n) = f(n) * TIME，可以看出代码执行时间与代码执行次数成正比，可以进一步表示为：T(n) = O( f(n) )，O表示T(n)与f(n)成正比。

上面那个例子用大O表示法就是T(n) = O(2n^2 + 2n + 1)，请注意，大O表示法其实不指代码的具体运行时间，而是表示代码执行时间随数据规模增长的变化趋势。

当数据规模很大时，也就是n很大时，公式中的常量、系数和低阶都可以忽略，因为此时这三部分对n的增长趋势影响。

最终，上面那个例子的大O复杂度表示法就是 T(n) = O( n^2 )。

常见时间复杂度

常见原则：

加法原则：

例如顺序执行三个循环，第一个循环执行100次，第二个循环执行n次，第三个循环执行n^{2次，T(n) = O(100 + n + n}2)，忽略常量和低阶就是T(n) = O( n^2 )。
乘法原则：

嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。例如两层嵌套循环，外层n次，内存n次，则T(n) = O(n * n)。

常见复杂度案例：

常量阶：O( 1 )，并不是代表只执行了1行代码，只要算法里没有循环和递归，哪怕顺序执行了一万行代码，也算O( 1 )。
对数阶：O( logn )、O( nlogn )，常见于递归树的分析，也是比较难分析的一类复杂度。
线性阶：O( n )，常见于循环遍历。
k方阶：O( n^{2 )、O( n}3 )、...O( n^k )，常见于嵌套循环。

以上罗列的复杂度量级可以称为多项式量级，另外还有两个非多项式量级：

指数阶O( 2^n ) 和阶乘阶O( n! )，非多项式复杂度是很低效的算法，不再展开细说。

END

为了不考虑机器配置和数据规模的差异所带来的影响，引入了时间复杂度这个概念。

而时间复杂度就是描述算法执行时间随数据规模增长所表现的趋势。

在学习算法的过程中，试着分析所学算法的时间复杂度，慢慢的会对时间复杂度有更深入的理解。