玩转数据结构之简单的复杂度分析

0. 序言

数据结构和算法解决的是“快"和"省"的问题，即"如何让代码运行得更快"以及"如何让代码更省内存空间"。而衡量代码运行时间的标准，我们称之为"时间复杂度";衡量代码占用空间的标准，我们称之为”空间复杂度"。

这篇文章通过简单的示例，带你入门复杂度分析，而更多的复杂度分析后续会写文章阐述。

1. 为何需要复杂度分析

你可能会对代码的复杂度分析有疑问，觉得代码的时间和空间复杂度通过代码的执行，并在此执行的过程中监控、统计就能获得，为何还要进行复杂度分析呢？不可否认，这也是一种计算代码时间和空间复杂度的方法，叫事后统计法，只是这种方法有局限性，因为这些局限性，会导致复杂度的统计不准确。

• 测试结果非常依赖测试环境
  测试环境中硬件的不同会对测试结果有很大影响。比如说i9和i3处理器处理同一段代码，i9的执行速度快很多。
• 测试结果受数据的影响很大
  拿排序来说：
  ① 同一个排序方法，数据有序度不一样的话，排序的执行时间就会有很大的差别。
  ② 小规模的数据排序，插入排序可能会比快速排序要快。

综上：我们需要一个不用具体的测试数据来测试，就可以粗略地计算代码的执行效率的方法，也就是这篇文章要讲解的时间和空间复杂度分析法。而时间和空间复杂度分析完毕后，我们总要阐述出来，而通常我们采用大O复杂度表示法来阐述时间和空间复杂度。

2. 大O复杂度表示法

 int cal(int n) {
   int sum = 0; // 1
   int i = 1; // 2
   for (; i <= n; ++i) { // 3
     sum = sum + i; // 4
   }
   return sum; // 5
 }

CPU在执行的过程中总是执行类似操作：读数据-运算-写数据。因为是粗略估计，所以我们可以忽略诸如CPU核数等差异条件。那么在这种粗略计算下，我们假设每行代码的执行时间相同，称之为unit_time，即单位时间。那以上代码的总执行时间是多少呢？

代码1和代码2以及代码5都需要一个单位时间unit_time,而代码3和代码4执行了n遍，都需要n个unit_time,这段代码执行总共需花费的时间是（3+2n）× 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;
     }
   }
 }

通过上面的分析，我们可以得出这段代码总执行时间T(n) = (2n²+2n+3)*unit_time。

综上：所有代码的执行时间T(n)与每行代码的执行次数成正比。用公式来表示：

T(n) = O(n)
① n：表示数据规模的大小。
② O：表示代码的执行时间T(n)与数据规模的大小成正比。

所以上面的示例用大O复杂度表示法表示分别是T(n) = O(3+2n)和T(n) = O(2²+2n+3).所以大O复杂度表示法并不具体表示真正的执行时间，而是表示代码的执行时间随数据规模增长的变化趋势，也叫做渐进时间复杂度，简称时间复杂度。所以当n很大的时候，公式中的常量、系数并不左右增长趋势，所以可以忽略，我们只记录一个最大量级就可以了，所以上面的示例用大O复杂度表示法也可以表示为：T(n) = O(n)和T(n) = O(n²).

3. 简单的时间复杂度分析

这里讲解代码时间复杂度分析的三个方法：

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

 int cal(int n) {
   int sum = 0; // 1
   int i = 1; // 2
   for (; i <= n; ++i) { // 3
     sum = sum + i; // 4
   }
   return sum; // 5
 }

这里代码1和2和5都是常量级的执行时间，而代码3和4循环次数最多，我们只关注循环执行次数最多的一段代码，所以总的时间复杂度是O(n)。

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

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;
 }

sum1段代码的时间复杂度是常量级，尽管是循环，但只要有明确的次数，代码的时间复杂度是O(1)。sum2段代码因为循环了n次，所以时间复杂度是O(n),同理sum3段代码的时间复杂度是O(n²)。根据加法法则：这三段代码的时间复杂度，加起来就是O(1)+O(n)+O(n²)，而我们取最大量级，所以这段代码的时间复杂度是O(n²)

• 乘法法则: 嵌套代码复杂度是嵌套内外代码复杂度的乘积

 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;
     }
   }

这段代码有两层嵌套，所以这段代码的复杂度是O(n * n) = O(n²)

4. 空间复杂度分析

时间复杂度，也叫做渐进时间复杂度，同样，空间复杂度，也叫做渐进空间复杂度，表示算法的存储空间与数据规模之间增长关系。

常见的空间复杂度有O(1),O(n),O(n²)，而O(logn)和O(nlogn)这样的对数阶复杂度平时用不上。

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]
  }
}

分析空间复杂度，就分析哪些代码占用内存。经过分析发现，以上代码中只有容量为n的数组和常量i占用空间，根据加法法则，这段代码的复杂度为O(n).

5. 后续

如果大家喜欢这篇文章，欢迎点赞！
如果想看更多 数据结构 方面的文章，欢迎关注!