数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量指标。

一.为何要进行复杂度分析

直接将代码跑一遍，统计得到算法运行的时间和内存占用，即事后统计法，存在以下局限：

• 测试结果受限于测试环境
• 测试结果受限于测试规模

因此，我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法。即大O表示法

二.时间复杂度分析

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

• 单段代码看高频：比如循环。
• 多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
• 嵌套代码求乘积：比如递归、多重循环等
• 多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。

三.空间复杂度分析

空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间随数据规模增长的变化趋势。

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

// 空间复杂度为O(n)

四.常用复杂度级别

常用的复杂度级别可粗略的分为多项式量级和非多项式量级

• 多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长
• 非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括，$O(2^n)$（指数阶）、$O(n!)$（阶乘阶）

$O(logn)$和$O(nlogn)$：在采用大 O 标记复杂度的时候，可以忽略系数，$O(Cf(n)) = O(f(n))$。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 $O(logn)$。

五.特殊情况下的复杂度

• 最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度
• 最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度
• 平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示。
• 均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有前后连贯的时序关系时，可以将个别高级别复杂度 均摊 到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

六.课后习题

// 全局变量，大小为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;
}

• 最好时间复杂度：没满，直接添加即可，$O(1)$
• 最坏时间复杂度：满了，需扩容和复制值，$O(len)$
• 均摊时间复杂度：每次$O(len)$的出现都跟着len次$O(1)$，是前后连贯的，因而将$O(len)$平摊到前len次上，得出平摊复杂度是$O(1)$
• 平均时间复杂度：当每次遇到最坏情况时数组会进行2倍扩容，原数组被导入新数组，虽然数组的长度变大了，但是插入操作落在的区间的长度是一样的，分别是0到len-1, len到$(2len-1)$….；
  插入的情况仍是len+1种：0~len-1和插满之后的$O(len)$；所以每次插入的概率是：p= 1/len+1，
  最后求出加权平均时间复杂度为 $(1 + 1+ …+ 1 + len) * p = O(1) $