复杂度分析

时间复杂度

时间复杂度$T(n)$： 根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。

大O表示法

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

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

时间复杂度分析

时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，由于常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响，所以在做时间复杂度分析时忽略这些项。

分析方法

• 只关注循环执行次数最多的一段代码

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

  第 2、3 行代码都是常量级的执行时间，与 n 的大小无关，所以对于复杂度并没有影响。循环执行次数最多的是第 4、5 行代码，所以这块代码要重点分析。这两行代码被执行了 n 次，所以总的时间复杂度就是 $O(n)$。

• 总复杂度等于量级最大的那段代码的复杂度

  int cal(int n) {
     int sum_1 = 0;
     int p = 1;
     for (; p < 100; ++p) {
       sum_1 = sum_1 + p;
     }
  
     int sum_2 = 0;
     int q = 1;
     for (; q < n; ++q) {
       sum_2 = sum_2 + q;
     }
   
     int sum_3 = 0;
     int i = 1;
     int j = 1;
     for (; i <= n; ++i) {
       j = 1; 
       for (; j <= n; ++j) {
         sum_3 = sum_3 +  i * j;
       }
     }
   
     return sum_1 + sum_2 + sum_3;
   }
  
  

  这个代码分为三部分，分别是求 sum_1、sum_2、sum_3。分别分析每一部分的时间复杂度，然后取一个量级最大的作为整段代码的复杂度。

  这三段代码的时间复杂度分别是是 $O(1)$、$O(n)$ 和 $O(n^2)$。

  综合这三段代码的时间复杂度，取其中最大的量级。所以，整段代码的时间复杂度就为$O(n^2)$。

• 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

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

  假设 f() 只是一个普通的操作，那第 4～6 行的时间复杂度就是，$T1(n) = O(n)$。但 f() 函数本身不是一个简单的操作，它的时间复杂度是 $T2(n) = O(n)$，所以，整个 cal() 函数的时间复杂度就是，$T(n) = T1(n) * T2(n) = O(n*n) = O(n^2)$。

  常见的复杂度量级

  **多项式阶：**随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。

  如： $O(1)$（常数阶）、$O(logn)$（对数阶）、$O(n)$（线性阶）、$O(nlogn)$（线性对数阶）、O(n^2)（平方阶）、$O(n^3)$（立方阶）等

  **非多项式阶：**随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。

  如：$O(2^n)$（指数阶）、$O(n!)$（阶乘阶） 等

  

空间复杂度

空间复杂度S(n)： 根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。

与时间复杂度类似，空间复杂度表示算法的存储空间与数据规模之间的增长关系，也叫作渐进空间复杂度（asymptotic space complexity）。记作:$S(n)=O(f(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(n^2)$，像 $O(logn)$、$O(nlogn)$ 这样的对数阶复杂度平时都用不到。

特殊时间复杂度

同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度，所以引入了这4个概念。代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。

最好最坏时间复杂度

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

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

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

此代码遍历一个长度为n的数组，查找某个值，查到了就退出。

如果数组中第一个元素正好是要查找的变量 x，那就不需要继续遍历剩下的 n-1 个数据了，那时间复杂度就是 $O(1)$，也就是最好情况时间复杂度。

但如果数组中不存在变量 x，那我们就需要把整个数组都遍历一遍，时间复杂度就成了 $O(n)$，也就是最坏的情况时间复杂度。

平均时间复杂度

平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示。

依然使用上面的查找数组的例子，要查找的变量 x 在数组中的位置，有 n+1 种情况：在数组的 0～n-1 位置中和不在数组中。假设在数组中与不在数组中的概率都为 1/2。而要查找的数据出现在 0～n-1 这 n 个位置的概率是一样的，为 $1/n$。所以，要查找的数据出现在 0～n-1 中任意位置的概率就是 $1/(2n)$。

去掉系数和常量，这段代码的加权平均时间复杂度为 $O(n)$。

均摊时间复杂度

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