时间复杂度和空间复杂度

本文内容是个人对王争老师极客时间《数据结构与算法之美》的总结文章目录时间复杂度和空间复杂度复杂度分析的原因时间复杂度分析时间复杂度量级（按数量级递增）嵌套代码时间复杂度分析其他复杂度分析法空间复杂度分析练习题总结时间复杂度和空间复杂度王争老师的数据结构与算法学习，每日更新学习笔记老师的语言为c++,自己使用python复杂度分析的原因由于测试结果非常依赖测试环境，测试结果手数据规模的影响很大，因此

luolita001

517人浏览 · 2020-08-10 00:01:37

luolita001 · 2020-08-10 00:01:37 发布

本文内容是个人对王争老师极客时间《数据结构与算法之美》的总结

时间复杂度和空间复杂度

王争老师的数据结构与算法学习，每日更新学习笔记
老师的语言为C,自己使用python

复杂度分析的原因

由于测试结果非常依赖测试环境，测试结果手数据规模的影响很大，因此需要一个不用具体的测试数据来测试算法执行效率的方法，就是时间复杂度分析和空间复杂度分析。

时间复杂度分析

时间复杂度表示代码执行时间随数据规模增长的变化趋势。可以解释说，代码的执行时间T(n)与每行代码的执行次数n成正比。

只关注循环次数最多的一段代码，例如：代码块中一段代码的时间复杂度为O(n)，另一段代码的时间复杂度为O(n^ 2)，则最后这段代码的时间复杂度为O(n^2).

符合加法算法和乘法算法。具体分析看以下代码部分。

时间复杂度量级（按数量级递增）

常数阶O(1) ：
执行常数次代码
对数阶O(logn)
例如下面代码，此代码的时间复杂度为O(log2n)。（2为底）
```
 i=1;
 while (i <= n)  {
   i = i * 2;
 }
```
线性阶O(n) ：执行代码次数与n有关
线性对数阶O(nlogn)
平方阶 O(n^2)，立方阶O(n ^3)，k次方阶O(n ^k)

指数阶O(2^n)
阶乘阶O(n!)

嵌套代码时间复杂度分析

普通嵌套

以下代码为C++写的for嵌套循环，每执行一次为O(1)的时间复杂度，前三行的时间复杂度为O(3)，每执行一次外层for循环，内层执行n次，时间复杂度为O(2n),外层for执行n次，时间复杂度符合加法算法和乘法算法，这段代码的时间复杂度为O(2n^2+2n+3)，只取高阶项且忽略系数，最后这段代码的时间复杂度为O(n ^2)。

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

含break等的特殊嵌套

代码如下，此时这段代码的时间复杂度

// 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的值有关，这种情况下的时间复杂度由四个量进行衡量：最好，最坏，平均，均摊时间复杂度

其他复杂度分析法

最好时间复杂度
最理想情况下，执行代码的时间复杂度（在上述代码中，最好情况x=array[1]，此时时间复杂度为O(1)）
最坏时间复杂度
在上述代码中，x不在数组中此时时间复杂度为O(n)
平均时间复杂度
求期望法：x在数组中和不在数组中的概率都为1/2，且x出现在数组中任意的概率相同，所以x出现在数组任意位置的概率为(1/2n)，位置一执行一次，位置二执行两次，。。。，不在数组内执行n次，可以得到平均时间复杂度如下:
1/2n+2/2n+3/2n+…+n/2n+n/2=（3n+1)/4，则平均时间复杂度为O(n)。
均摊时间复杂度
均摊时间复杂度就是把每次执行n次摊还到执行一次上。
```
 // array表示一个长度为n的数组
 // 代码中的array.length就等于n
 int[] array = new int[n];
 int count = 0;
 
 void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

    array[count] = val;
    ++count;
 }
```
以上代码实现了往数组中插入数据的功能。当数组满了后，即当count==array.length时，进入for循环遍历数组求和，并清空数组将求婚之后的sum值放在数组的第一个位置，然后再将新的数据插入。但如果数组存在空闲空间则直接将数据插入数组
- 平均时间复杂度
x出现在各位置的概率为1/(n+1),包括当数组满时。数组未满时执行次数都为1，数组满时执行次数为n，最后可以得到1*n/(n+1)+n/n+1=2n/(n+1)，则平均时间复杂度为O(1)。
- 均摊时间复杂度
将数组满时执行次数n均摊到数组未满时执行次数为1，则均摊时间复杂度为O(1)

空间复杂度分析

代码中数组，空间复杂度为数组的空间复杂度
一维数组：O(n)
二维数组：O(n^2)
代码中有递归
递归的深度为空间复杂度
既有递归又有数组
两者中复杂度最大的为空间复杂度

练习题


// 全局变量，大小为10的数组array，长度len，下标i。
int array[] = new int[10]; 
int len = 10;
int i = 0;

// 往数组中添加一个元素
void add(int element) {
   if (i >= len) { // 数组空间不够了
     // 重新申请一个2倍大小的数组空间
     int new_array[] = new int[len*2];
     // 把原来array数组中的数据依次copy到new_array
     for (int j = 0; j < len; ++j) {
       new_array[j] = array[j];
     }
     // new_array复制给array，array现在大小就是2倍len了
     array = new_array;
     len = 2 * len;
   }
   // 将element放到下标为i的位置，下标i加一
   array[i] = element;
   ++i;
}