数据结构和算法的目的是让代码运行的更快或让代码更节省存储空间，根据不同的场景与需求获得一个最均衡的结果。

而这个"快" 与 "省" 需要指标进行衡量，也就是时间、空间复杂度分析。

学习算法与数据结构离不开时间、空间复杂度分析，因为需要用指标去衡量效率，而复杂度分析是算法学习的精髓，掌握了分析复杂度的方法，数据结构与算法的内容就掌握了一半。

为什么需要分析复杂度？

如果不使用复杂度分析：

事后统计法：通过运行代码，统计、监控代码的运行时间和占用大小得出代码的时间、空间统计结果。

但是这种方法有两个非常大的局限性：

  • 测试结果依赖测试环境
  • 测试结果受规模数据影响很大

1. 测试结果非常依赖测试环境

测试环境中硬件的不同会对测试结果造成巨大的影响，同样的代码跑在 i3 和 i9 的机器上得出的结果截然不同，两段代码， a 的效率比 b 要高，但是将 b 代码跑在高配的机器上，可能用时比 a 还要短。

【那控制变量不就好了？将 a,b 都跑在一样的机器上，但是有种情况就是数据量不大的时候，算法效率差距不大，当数据量极大时，算法差距会呈指数形式，所以我们需要的不是具体的执行时间，是一种抽象的效率表达式】

2. 测试结果受数据规模影响很大

作者以排序算法举例，同一个排序算法，待排序数据的有序度不一样，排序的执行时间会有很大差别。

极端情况下，待排序数据已经有序，则算法不用做任何操作，执行时间会非常短，除此之外，如果数据规模太小，则可能无法反应算法的真实性能：

  • 小规模的数据排序，插入排序可能比快排更快。

所以需要一个不用具体的测试数据来测试，而是粗略估计算法执行效率的方法 —— 时间、空间复杂度分析方法。

大 O 复杂度表示法

在不运行代码的前提下，用肉眼得到一段代码的执行时间的方法。

下面有段非常简单的代码：1,2,3...n的累加求和，作者将会分析这段代码的复杂度

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

从 CPU 的角度来看，这段代码的每一行都执行类似的操作：读数据-运算-写数据。虽然每行代码的对应的 CPU 执行个数，执行时间都不同，但是在粗略估计的前提下，可以假设每行代码执行时间一样，是一个单位时间 unit_time。在这个假设的基础上，去估计上面这段代码的总执行时间：

第2、3行分别需要 1 个 unit_time 执行时间，4、5 行运行了 n 遍，需要 2n * unit_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^2 遍，需要 2n^2 * unit_time 执行时间

总执行时间 T(n) = (2n^2 + 2n + 3) * unit_time

虽然不知道 unit_time 的具体值是多少，但是通过代码的执行推导过程，可以得到非常重要的规律：所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

T(n) = O(f(n)) ，下面是这个表达式的详解：

  • T(n) --> 代码执行时间

  • n --> 数据规模大小

  • f(n) --> 每行代码执行的次数总和

  • O --> 在上个表达式中表示 代码执行时间 T(n) 与 f(n) 成正比

第一个例子 T(n) = O(2n+2)，第二个例子 T(n) = O(2n^2 + 2n + 3)，这就是 大 O 时间复杂度表示法。 大O 的时间复杂度并不是代码真正的具体时间，而是代表代码执行时间随数据规模增长的变化趋势，也被称为渐进时间复杂度(asymptotic time complexity)，简称为 时间复杂度。

当 n 很大时，可以想象成 10,000 、 10,000,000，公式中的 低阶、常量、系数 并不左右增长趋势，可以忽略。我们只需要记录 最大量级，用 大O 表示法表示刚才两端代码的复杂度，分别记录为：

  • T(n) = O(n)
  • T(n) = O(n^2)

时间复杂度分析

上面介绍了 大O 的由来和表达式的含义，下面是如何分析时间复杂度，具体有3个方法。

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

大 O 复杂度表示法表示的是一种变化趋势。通常会将常量、低阶、系数忽略，只记录最大阶的量级。

分析一个算法、一段代码时，只关注循环执行次数最多的代码即可，这段核心代码执行次数的 n 的量级，就是整段要分析代码的时间复杂度。

重新使用上面的例子举例：

int cal(int n) {
  int sum = 0;
  int i = 1;
  for (; i <= n; ++i) {
    sum = sum + 1;
  }
  return sum;
}
  • 2、3行执行赋值操作，耗费的是常量的执行时间，与数据规模 n 无关，对于复杂度分析没有影响
  • 循环执行次数最多的代码是 4、5行 for 循环代码，所以这块需要重点分析，这两行代码被循环了 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;
}

个人分析：

  • 第一段复杂度是常数：100，所以直接忽略

  • 第二段是 O(n) 复杂度

  • 第三段循环是复杂度量级最大的循环，所以直接分析第三段循环即可，第三段做了 for 循环嵌套，每次的复杂度是 O(n) ，所以总复杂度是 O(n^2)。

作者分析：

与我的分析一致，又重新声明了一遍时间复杂度的概念：

  • 表算法执行效率与数据规模增长的变化趋势，所以常量可以忽略。

如果 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))

乘法法则可以看做代码中的嵌套循环。

// 这里调用了另外一个函数 f()，所以可以看做是循环
int cal(int n) {
  int ret = 0;
  int i =1;
  // for 循环本身复杂度为 O(n) ，循环中调用了 复杂度为 O(n) 的 f() 
  // 所以最终 cal() 的复杂度为 O(n^2)
  for (; i < n; ++i) {
    ret = ret + f(i);
  }
}

// 复杂度为 O(n)
int f(int n) {
  int sum = 0;
  int i =1;
  for (; i <= n; ++i) {
    sum = sum + i;
  }
  return sum;
}

【作者的分析和我的相同，我的分析已经使用注释的方式写在上面的代码中了。】

几种常见的复杂度分析实例

代码的差别虽然大，但是复杂度的量级并不多，下面几种是常见的复杂度量级，几乎涵盖所有接触到的代码：

  • 常量级 —— O(1)
  • 指数级 —— O(2^n)
  • 对数级 —— O(log(n))
  • 线性级 —— O(n)
  • 线性对数 —— O(nlogn)
  • 平方级 —— O(n^2)
  • 立方级 —— O(n^3)
  • k次方级 —— O(n^k)
  • 阶乘级 —— O(n!)

上面列举的复杂度量级可以粗略分为**两类**：多项式量级和非多项式量级。

非多项式量级只有两个：

  • 指数级 —— O(2^n)
  • 阶乘级 —— O(n!)

非多项式量级的算法被称为 **NP（Non-Deterministic Polynomial ，非确定多项式）**问题。

当数据规模 n 越来越大时，非多项式量级的算法执行时间会急剧增加，求解问题的执行时间会无限增长，所以非多项式复杂度的算法是非常低效的算法。

下面是常见的多项式时间复杂度的详细分析：

1. O(1)

首先需要明确概念：O(1) 是常量级时间复杂度的一种表示方法，而不是指真的只执行了一行代码。下面这段代码，即便有 3 行，它的时间复杂度也是 O(1) 而不是 O(3)。

int i = 8;
int j = 6;
int sum = i + j;

只要代码的执行时间不随 n 的增加而增加，这样的代码时间复杂度都是 O(1)。一般情况下，算法中不存在循环语句、递归语句，即使代码再多，时间复杂度也是 O(1)。

【反过来说，尽量避免循环和递归的存在。】

2. O(logn)、O(nlogn)

对数阶复杂度很常见，同时也是最难分析的一种。

i =  1;
while (i <= n) {
  i = i * 2;
}

根据之前的分析，第三行代码循环执行次数最多，所以要分析这段代码的时间复杂度只需要分析这一行的代码被执行了多少次即可。

从代码可以看出， 变量 i 从 1开始取值，每次循环 乘 2，当大于 n 时，循环结束。这其实就是高中的等比数列，变量 i 的取值是一个等比数列，一个个列出来的话应该是下面这样：

image-20200923150532073

只需要知道 x 的值，就可以知道这行代码的执行次数了。 通过 2 ^ x = n 求解

image-20200923150719717

得出：

image-20200923150740018

所以这段代码的复杂度就是 O(log2n)

将代码稍微改动一下，试着分析复杂度：

i = 1;
whiel (i <= n) {
  i = i * 3;
}

根据上面的思路，分析很简单 ： O(log3n)

不管以 2 为底，还是以 3 为底，甚至是以 10 位底，所有对数级的时间复杂度都是 O(logn)。

因为对数之间可以互相转换 ：
image-20200923152025157

所以
image-20200923153131067

其中

是一个常量，基于前面的理论，采用 大 O 标记复杂度时，可以忽略系数 即 O(Cf(n)) = O(f(n)) 。

所以

因此在对数阶复杂度表示方法里，忽略对数的底，统一表示为 O(logn)

3. O(m+n)、O(m*n)

下面是一种和之前不一样的时间复杂度，代码的复杂度由两个数据的规模决定，看下面的代码：

int cal(int m, int n) {
  int sum_1 = 0;
  int i  = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }
  
  int sum_2 = 0;
  int j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }
  
  return sum_1 + sum_2;
}

这里 m 和 n 表示两个数据规模，并且这两个参数无法事先评估谁的量级更大。所以在表示复杂度时不能简单地像之前使用加法法则那样，直接忽略掉一个，所以上面代码的时间复杂度是 O(m + n)

针对上面这种有两个数据规模且无法事先评估大小的情况，之前的加法法则就不适用了，需要将加法规则修改为 ：

T1(m) + T2(n) = O(f(m) + g(n))

但是乘法法则仍然有效：

T1(m) * T2(n) = O(f(m) * f(n))

空间复杂度分析

前面花了大量的篇幅讲解 大 O 复杂度的概念与计算方法，理解了之后学习后面的空间复杂度就会比较简单。

时间复杂度的全称是：渐进时间复杂度，表示算法执行时间与数据规模之间的增长关系。

类比一下，空间复杂度就是 —— 渐进空间复杂度（asymptotic space complexity)，表示算法的存储空间与数据规模之间的增长关系。

下面是示例代码：

void print(int n) {
  int i = 0;
  int[] a = new int[n];
  for (i; i < n; ++i) {
    a[i] = i * i;
  }
  for (i = n-1; i >= 0; --i) {
    print out a[i];
  }
}

与分析时间复杂度一样：

  • 第 2 行代码申请了一个空间存储变量 i，但是是常量级，所以可以忽略。
  • 第3行申请了一个大小为 n 的 int 类型数组，除此之外，代码没有占用更多的空间，所以这段代码的空间复杂度是 O(n)

常见的空间复杂度：

  • O(1)
  • O(n)
  • O(n^2)

复杂度对数复杂度： O(logn)、O(nlogn)平时用不到，并且空间复杂度的分析比时间复杂度分析简单很多，掌握上面的已经够了。

内容小结

复杂度全称 —— 渐进复杂度，包含空间和时间两个维度，用来分析算法执行效率与数据规模之间的增长关系。

可以粗略的表示：复杂度越高阶的算法，效率越低，常见的复杂度不多，从低到高：

  • O(1)
  • O(logn)
  • O(n)
  • O(nlogn)
  • O(n^2)

基本上常用的数据结构与算法都在上面几种复杂度范围之内。

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

最是人间留不住，曾是惊鸿照影来。