算法-复杂度分析

前言

我们都知道，数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行的更快、更省存储空间。那如何来衡量算法的“快”和“省”呢？这就要用到复杂度分析：时间、空间复杂度分析。复杂度分析是整个算法学习的精髓，掌握了它，数据结构和算法的内容基本就掌握了一半。

为什么需要复杂度分析

有人说，我只要把代码跑一遍，通过统计、监控，就可以得到算法执行的时间和占用的那内存，为什么还要做复杂度分析呢？

1、首先，这种评估方法确实是准确的，但是这种方法是”事后统计法”，是有非常大的局限性。
2、测试结果非常依赖测试环境，同样一段代码，在不同的CPU可能执行的时间会差很多，比如Intel Core i9就比i3运行的快，同样在不同的两台机器上也可能会出现代码执行不一样的情况。
3、对于不同的数据集，如果数据的有序程度不一样，那么对数据进行同一种算法运算，也可能会得到不同的结果。除此之外，数据规模的大小也可能对算法产生影响。

因此我们需要一个不用具体的测试数据来测试，就可以粗略估计算法的执行效率的方法，这就是时间、空间复杂度分析所解决的问题。

大O复杂度表示法

算法的执行效率，粗略的讲，就是算法执行的时间，但是如何能在不运行的情况下，得到一段代码的运行时间呢？

这里举一个简单的例子，求解1，2，3……n 的累加和，以下为一个简单的代码实现：

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

从CPU的角度看，每一行代码都执行着类似的操作：读数据-运算-写数据。尽管每行代码对应的CPU执行个数、执行时间都不尽相同，但是我们只是粗略的估计，因此这里假设每行代码执行的时间都相同，那么在此基础上，这段代码执行的时间可以进行如下计算：

第二行代码执行时间为time，第三、四行代码执行的时间为 $ 2 \times n \times time $，所以此段代码执行的时间为$ (2n + 1)\times time $ ，可以看出这段代码执行时间T(n)与每行代码的执行次数成正比。

按照这个思路，再对以下代码段进行分析：

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

假设每行代码执行的时间依然为time，那么这段代码执行的时间是多少呢？

第二行代码的执行时间依然为time，第三行代码执行的次数为n次，所以需要的时间为$ n*time $,内层循环第四、五行代码都执行了$ n*n $次,需要的时间为$ 2*n^2*time $。所以此段代码总的执行时间为$(n + 1 + 2n^2)*time $。

尽管不知道time的具体值，但是通过这两段代码的分析过程，得出一个非常重要的规律：

所有的代码执行时间T(n)与每行代码的执行次数成正比
$$ T(n) = O(f(n)) $$

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

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

在时间复杂度公式中，如果n很大时，公式中的低阶、常量、系数三部分并不影响增长趋势，所以可以先忽略。所以上述两个例子的时间复杂度就可以记为： $ T(n) = O(n) $； $ T(n) = O(n^2) $;

时间复杂度分析

前面介绍了大 O 时间复杂度的由来和表示方法，那如何分析一段代码的时间复杂度呢？

1、只关注循环次数最多的一段代码

在大 O 表示法中，只是表示一种趋势，通常我们会忽略公式中的常量、低阶、系数，因此只需要记录一个最大的量级就可以了，所以我们在分析一个算法时，只关注循环次数执行次数最多的那一段代码就行了。

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

如果一段代码中出现多个循环，那么总的时间复杂度就是各个循环相加得到的，但是往往会忽略低阶、常量，因此只取量级最大的那段代码就可以了。

注意：
当一段代码循环次数是一个常量，比如循环10000、1000000次，只要是一个已知的常量数，且不随数据规模变化，那么该循环照样是一个常量级别的执行时间。

3、乘法法则: 嵌套代码的时间复杂度等于嵌套内外代码复杂度的乘积

比如第二个例子中如果但看外层循环的时间复杂度是 $ O(n) $；内层循环的时间复杂度也是 $O(n)$，因此总共的时间复杂度就是 $ T(n) = O(n) * O(n) = O(n^2) $

几种常见时间复杂度

1、$O(1)$

O(1) 只是常量级时间复杂度的一种表示方法，并不是指执行了一行代码。只要代码的执行时间不随n的增大而增大，这样的代码时间复杂度都可以记为O(1)。一般情况下，只要代码中不出现循环、递归等，即使有成千上万行代码，时间复杂度也是O(1)。

2、$ O(logN)、O(N*logN) $

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

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

在上述代码中，变量i从1取值，第二次为2，第三次为4，第四次为8……,所以i的取值规律为 $$ 2^0 \ 2^1 \ 2^2 \ 2^3 … 2^k… 2^x $$ 当$2^x = n$ 时，循环结束，而循环的次数即为x，所以时间复杂度也为$ O(x=\log_2 N) $。

如果把代码改为如下。那时间复杂度是多少呢？

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

根据上面的思路，很容易看出这段代码的时间复杂度为$ O(log_3N) $ 。

实际上，不管是以2为底，还是以3为底，亦或是以10为底，我们都把对数阶的时间复杂度记为$ O(logN) $，为什么呢？

我们知道对数之间是可以互相转化的，$ log_3n$ 就可以转换为$ log_32*log_2N $，所以$ O(log_32) = O(C * log_2N) $，其中$ C = log_32 $ 是一个常量，基于前面的结论： 在采用大O标记复杂度的时候，可以忽略系数，即$ O(C*f(n)) = O(f(n)) $。因此在对数阶时间复杂度的表示方法里，我们忽略的底，统一表示为$O(logN)$。

如果理解了$O(logN)$，那么$O(nlogN)$就很容易了，根据前面所说的乘法法则，如果一段代码的时间复杂度是$O(logN)$，如果循环执行了 n 次，那么该代码的时间复杂度就是$O(nlogN)$。而且$O(nlogN)$是一种非常常见的时间复杂度，归并排序、快速排序的时间复杂度都是$O(nlogN)$。

2、$ O(m+n)、O(m*n) $

我们再来讲跟前面都不一样的时间复杂度，代码的时间复杂度由两个数据规模来决定。

int func(int m, int n){
  int sum1 = 0;
  for(int i=1; i<=m; i++){
    sum1 += i;
  }

  int sum1 = 0;
  for(int j=1; j<=m; j++){
    sum1 += j;
  }
  return sum1+sum2;
}

从代码中看出，m和n表示两个不同的数据规模，我们无法事先评估m和n的量级大小，所以我们在分析复杂度时，就不能简单用加法法则忽略一个，因此上面代码的时间复杂度为$O(m + n)$，

针对这种情况，加法原则就不正确了，我们将加法原则改为：$ T1(m) + T2(n) = O(f(m) + g(n)) $，但是乘法法则继续有效：$ T1(m) + T2(n) = O(f(m) * f(n)) $。

空间复杂度

前面讲过，时间复杂度的全称是渐近时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度的全称就是渐进空间复杂度，表示算法的存储空间与数据规模的增长关系。

还是拿具体的例子说明(仅供测试,一般没人这么写)

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

和分析时间复杂度一样，我们看到第二行申请了一个空间变量i，但是它是常量阶的，跟数据规模n无关，所以可以忽略，第三行申请了一个大小为n的int数组，除此之外，该代码没有占据更多的空间O(n).

我们常见的空间复杂度就是$O(1)、O(n)、O(n^2)$，像$ O(logN)、O(nlogN) $ 这样的对数阶复杂度平时都用不到。空间复杂度分析相对时间复杂度要简单得多。