【数据结构和算法】复杂度分析

2016-12-02

前言

我们都知道，数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行的更快，如何让代码更省存储空间。所以执行效率是考察算法的一个衡量指标，我们在面试的时候，都要求我们写一个最优算法，就是指效率最优的算法。那如何衡量算法的执行效率，就是衡量算法的时间、空间复杂度。

大O复杂度表示法

算法执行效率，粗虐的讲就是算法代码执行时间。我们在不运行代码的情况下，如何用“肉眼”得到一段代码的执行时间呢？

例如下面一段代码，求1,2,3…n的累加的和。

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

从CPU的角度看，这段代码的每一行都执行着类似的操作：读数据-运算-写数据。尽管每行代码对应的CPU执行次数、执行时间都不一样，但是，我们这里只是粗略的估计，所以可以假设每行代码时间都一样，为unit_time。在这个假设基础之上，这段代码总执行时间是多少呢？

第2、3行代码分别需要1个unit_time的执行时间，第4、5行都运行了n遍，所以需要2nunit_time的执行时间，所以这段代码的执行时间就是(2n+2)unit_time。可以看出来，所有代码的执行时间T(n)与每行代码的执行次数成正比。

下面在看一段代码，分析一下复杂度：

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

还是假设每行代码执行的时间是unit_time，这段代码第2、3、4行都是需要1个unit_time，第5、6行代码执行了n遍，需要2n unit_time的执行时间，第7、8行代码执行了n²遍，所以需要2n²unit_time的执行时间。所以，整段代码总的执行时间就是T(n) = （2n² + 2n + 3）*unit_time。

尽管我们不知道unit_time的具体值，但是通过这段代码执行时间的推导过程，我们可以得到一个非常重要的规律，就是，所有代码的执行时间T(n)与每行代码的执行次数n成正比。

我们可以把这个规律总结成一个公式。

T(n)表示代码执行时间，n表示数据规模大小，f(n)表示每行代码的执行的次数总和。因为这是一个公式，所以用f(n)来表示。公式中的O，表示代码的执行时间T(n)与f(n)表达式成正比。

所以，第一个例子中的T(n) = O(2n+2),第二个例子中的T(n) = O（2n² + 2n + 3）。这就是大O时间复杂度表示法。大O时间复杂度实际上并不是具体表示代码的真正的执行时间，而是表示代码执行时间随着数据规模增长的变化趋势，所以，这也叫做渐进时间复杂度，简称时间复杂度。

当n很大时，你可以把它想象成10000,1000000.而公式中的低阶、常量、系数三分部并不是左右增长趋势，所以都可以忽略。而且门只需要记录一个最大的量级就可以了，如果采用大O表示法表示刚刚那两端时间复杂度就可以表示为：T(n) = O(n);T(n) = O(n²)。

时间复杂度分析

1.只关注循环执行次数最多的一段代码

大O这种复杂度表示方法只是表示一种变化趋势。我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。所以在分析一个算法，一段代码的时间复杂度的时候，也只需要关注循环次数最多的那一段代码就可以了。这段核心代码执行次数的n的量级，也就是整段要分析代码的时间复杂度。

看个例子：

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

其中第2、3行代码都是常量级别的执行时间，与n的大小无关，所以对于复杂度并没有影响。循环执行次数最多的是第4、5行代码，所以这块要重点分析。前面也说过这两行代码被执行n次，所以总的复杂度就是O(n)。

2.加法规则：总复杂度等于量级最大的那段代码的复杂度

看个例子：

int cal(int n) {
   int sum_1 = 0;
   int p = 1;
   for (; p < 100; ++p) {
     sum_1 = sum_1 + p;
   }

   int sum_2 = 0;
   int q = 1;
   for (; q < n; ++q) {
     sum_2 = sum_2 + q;
   }

   int sum_3 = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
     j = 1;
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
   }

   return sum_1 + sum_2 + sum_3;
 }

这段代码分为三个部分，分别是求sum_1,sum_2,sum_3。我们可以分别分析每一部分的时间复杂度，然后把他们放到一块，在取一个量级最大的作为整段代码的复杂度。
第一段代码的复杂度是执行100次，所以是一个常量的执行时间，跟n的规模无关。即便这段代码循环1000000次，只要是一个已知的数就跟n无关，照样也是常量级的执行时间，当n无限大的时候，就可以忽略。
第二段和第三段代码的时间复杂度是O(n)和O(n²)，也就很容易分析出来。
综合这三段代码的时间复杂度，我们取其中最大的量级。所以整段代码的时间复杂度就是O(n²)。也就是说：总的时间复杂度就等于量级最大的那段代码的时间复杂度。我们将这个规律抽象成公式就是：
如果T1(n)=O(f(n)),T2(n)=O(g(n)),那么T(n)=T1(n)+T2(n)=max(O(f(n)),O(g(n))=O(max(f(n),g(n)))。

3.乘法规则：嵌套代码的复杂度等于嵌套内外代码的复杂度乘积

如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)g(n)).
也就是说，假设 T1(n) = O(n)，T2(n) = O(n2)，则 T1(n) T2(n) = O(n3)。

几种常见时间复杂度实例分析

多项式量级和非多项式量级其中费多项式量级只有两个：O(2n)和O（n!)

内容小结

复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率和数据规模之间的增长关系，可以粗略表示，越高阶复杂度的算法，执行效越低。从低阶到高阶常见的有：O(1)、O(logn)、O(n)、O(nlogn)、O(n²）