算法的复杂度分析

我不是女神ヾ 2022-05-03 05:58 214阅读 0赞

# 复杂度分析是什么 #

代码的复杂度分为**时间复杂度**与**空间复杂度**。

数据结构与算法解决的核心问题就是让代码更“快”、更“省”。具体来说，就是执行的时间尽可能的短，占用的空间尽可能的少。

而代码到底有多“快”、有多“省”，需要对应的衡量标准，时间复杂度就作为代码有多“快”的衡量标准，空间复杂度就作为有多“省”的衡量标准。

对时间复杂度与空间复杂度的计算分析就是复杂度分析了。

# 为什么需要复杂度分析 #

我记得我刚接触到时间复杂度这个概念时就有这个疑问：明明可以让代码跑一下来看下它具体的执行时间，以此作为它的时间复杂度不好吗？毕竟这样的跑出来的结果是最为真实的。

这样来作为一段代码的具体执行时间也是可以的，不过不够精确，有很大的局限性。

首先这种直接跑出来的时间非常依赖测试环境，很显然，高端CPU跑一段代码的时间一定是少于普通CPU的。另外，测试结果会受数据规模的影响，在数据量不同的情况下，测试出代码执行的时间一定也是不同的，数据量小的情况下是很难测出一个算法的性能的。

鉴于此，需要从代码本身来分析它的复杂度。从而判断一个算法在时间、空间上的优劣。

# 时间复杂度分析中的代码执行时间 #

我们先来看一下如何判断一段代码的执行时间。

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 t t，那么代码运行的总时间就是 n ∗ t n\*t n∗t， n n n是语句的数量。

当然，这样的方式并不精确，因为一条语句执行的时间我们并不能精确的估计出，且每条语句的执行时间也不相同。

不过，这种分析法的核心就在于抓住次数这一主要矛盾，忽略每条语句所受环境影响造成的执行时间不同的这一次要矛盾。

接着看上述代码：  
第2、3、4条语句各执行一次，第5、6条语句各执行 n n n次，第7和第8条语句各执行 n 2 n^2 n2次。所以，总的语句执行次数为 ( 2 n 2 + 2 n + 3 ) (2n^2+2n+3) (2n2\+2n\+3)。

假设一条语句执行时间为t，那么总的执行时间 T ( n ) = ( 2 n 2 + 2 n + 3 ) t T(n)=(2n^2+2n+3)t T(n)=(2n2\+2n\+3)t。

# 大O复杂度表示法表示时间复杂度 #

前面代码的总的执行时间 T ( n ) = ( 2 n 2 + 2 n + 3 ) t T(n)=(2n^2+2n+3)t T(n)=(2n2\+2n\+3)t，那么可以看出来， T ( n ) T(n) T(n)是代码中语句执行次数n的函数。用大O复杂度来表示时间复杂度则为 T ( n ) = O ( n 2 ) T(n)=O(n^2) T(n)=O(n2)。

大O复杂度表示的并不是一段代码的真实运行时间，没有实际的测试环境也得不出它的实际运行时间。大O复杂度实际上表示的是**代码的执行时间随数据规模增长的变化趋势**。这也就是为什么 2 n 2 + 2 n + 3 2n^2+2n+3 2n2\+2n\+3可以只表示为 n 2 n^2 n2。因为在 n n n非常大的情况下，常量、系数、低阶都是可以忽略不计的。所以说，假设这段代码的总执行时间 T ( n ) = ( 10 n 2 + 9 n + 100 ) t T(n)=(10n^2+9n+100)t T(n)=(10n2\+9n\+100)t，依然可以用大O复杂度表示法表示为 T ( n ) = O ( n 2 ) T(n)=O(n^2) T(n)=O(n2)。

# 时间复杂度分析 #

分析时间复杂度记住三个方法：

1.  只关注循环次数最多的一段代码
2.  加法法则：总复杂度等于量级最大的那段代码的复杂度（多段代码）
3.  乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

# 常见时间复杂度 #

O ( 1 ) 、 O ( n ) 、 O ( n 2 ) 、 O ( l o g n ) 、 O ( n l o g n ) O(1)、O(n)、O(n^2)、O(logn)、O(nlogn) O(1)、O(n)、O(n2)、O(logn)、O(nlogn)  
 O ( 1 ) 与 O ( n ) O(1)与O(n) O(1)与O(n)： O ( 1 ) O(1) O(1)并不是指一段代码中只有一个语句执行了一次，而是语句的执行次数是常量，与输入数据规模无关。而 O ( n ) O(n) O(n)指代码的执行时间与数据规模 n n n成正比关系。

# 最好、最坏情况时间复杂度 #

最好、最坏情况时间复杂度顾名思义就是在最好与最坏的情况下，一段程序所会得到的时间复杂度。

// n 表示数组 array 的长度
    int find(int[] array, int n, int x) {
      int i = 0;
      int pos = -1;
      for (; i < n; ++i) {
        if (array[i] == x) {
           pos = i;
           break;
        }
      }
      return pos;
    }

最好时间复杂度：x为array\[0\]，这时的时间复杂度为O(1)。这时就是最好时间复杂度。  
最坏时间复杂度：x为array\[n\]，这时的时间复杂度为O(n)。这时就是最坏时间复杂度。

# 平均时间复杂度 #

最好和最坏时间复杂度表示的是一段程序在极端情况下会出现的时间复杂度，而平均时间复杂度的引入是为了表示一段程序在平均情况下的时间复杂度。

对于上面的示例代码来说，在x处于数组array之中时，会出现的查找次数分别为1、2、3、……、n，而x不处于数组array之中时，会出现的查找次数为n。

我们假设x处于数组array之中与不处于array之中的概率相同。那么我们会得到需要遍历的元素个数的平均值为 3 n + 1 / 4 3n+1/4 3n\+1/4，最终的平均时间复杂度为O(n)。

# 均摊时间复杂度 #

均摊时间复杂度是一种特殊的平均时间复杂度。

对于一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的诗序关系。这时就可以把较高的时间复杂度分摊到较低的时间复杂度。一般情况下均摊时间复杂度就等于最好时间复杂度。