时间、空间复杂度分析

偏执的太偏执、 2023-07-25 14:24 78阅读 0赞

## 时间复杂度 ##

`时间复杂度`表示算法的执行时间与数据规模之间的增长关系。

虽然代码千差万别，但是常见的复杂度量级并不多。我稍微总结了一下，这些复杂度量级几乎涵盖了你今后可以接触的所有代码的复杂度量级。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNDA0Mzk1_size_16_color_FFFFFF_t_70]

#### O(1) ####

首先你必须明确一个概念，O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如这段代码，即便有 3 行，它的时间复杂度也是 O(1），而不是 O(3)。

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

我稍微总结一下，只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。或者说，一般情况下，`只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)`。

#### O(logn)、O(nlogn) ####

对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。我通过一个例子来说明一下。

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

只要能计算出这行代码被执行了多少次，就能知道整段代码的时间复杂度。  
从代码中可以看出，变量 i 的值从 1 开始取，每循环一次就乘以 2。当大于 n 时，循环结束。还记得我们高中学过的等比数列吗？实际上，变量 i 的取值就是一个等比数列。如果我把它一个一个列出来，就应该是这个样子的：![在这里插入图片描述][20200415175424297.png]  
通过 `2^x=n` 求解 x 这个问题我们想高中应该就学过了，我就不多说了。`x=log2n`，所以，这段代码的时间复杂度就是 `O(log2n)`。

#### 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 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是 `O(m+n)`。

--------------------

## 空间复杂度分析 ##

`空间复杂度分析`表示算法的存储空间与数据规模之间的增长关系。其实就是主要关心变量占用的空间。

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，但是它是常量阶的，跟数据规模 n 没有关系，所以我们可以忽略。第 3 行申请了一个大小为 n 的 int 类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 O(n)。

我们常见的空间复杂度就是 `O(1)、O(n)、O(n2)`，空间复杂度分析比时间复杂度分析要简单很多。所以不在赘述。

--------------------

## 扩展概念 ##

###### 1.最坏情况时间复杂度： ######

代码在最坏情况下执行的时间复杂度。

###### 2.最好情况时间复杂度： ######

代码在最理想情况下执行的时间复杂度。

###### 3.平均时间复杂度： ######

用代码在所有情况下执行的次数的加权平均值表示。

###### 4.均摊时间复杂度： ######

在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNDA0Mzk1_size_16_color_FFFFFF_t_70]: /images/20230528/6450bae0477d4d0eb0dd2aa430bd1bd2.png
[20200415175424297.png]: /images/20230528/2314dee697124a879bf1e80f6d998a3b.png