复杂度分析

大 O 复杂度表示法

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

时间复杂度分析

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

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

时间复杂度：$O(n)$

2、加法法则：总复杂度等于量级最大的那段代码的复杂度

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

时间复杂度：$O(n^2)$

3、 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

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

$T(n) = T1(n) *T2(n) = O(n*n) = O(n^2)$

时间复杂度：$O(n^2)$

几种常见时间复杂度实例分析

• 常量阶 $O(1)$
• 对数阶 $O(logn)$
• 线性阶 $O(n)$
• 线性对数阶 $O(nlogn)$
• 平方阶 $O(n)$、立方阶 $O(n^3)$、k 次方阶 $O(n^k)$
• 指数阶 $O(2^n)$
• 阶乘阶 $O(n!)$

对于上面的复杂度量级，可以粗略地分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：$O(2^n)$ 和 $O(n!)$。

我们把时间复杂度为非多项式量级的算法问题叫作 NP（Non-Deterministic Polynomial，非确定多项式）问题。当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。

$O(1)$

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

一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是 Ο(1)。

$O(logn)$、$O(nlogn)$

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

变量 i 的值从 1 开始取，每循环一次就乘以 2，实际上 i 的取值就是一个等比数列，那么也就相当于$2^x = n$，$x = log_2n$，所以，这段代码的时间复杂度就是 $O(log_2n)$

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

同理，这段代码的时间复杂度为 $O(log_3n)$。

实际上，不管是以 2 为底、以 3 为底，还是以 10 为底，我们可以把所有对数阶的时间复杂度都记为 $O(logn)$。因为对数之间是可以互相转换的，$log_3n = log_32 * log_2n$，在采用大 O 标记复杂度的时候，可以忽略系数，即 $O(Cf(n)) = O(f(n))$，因此统一标记为 $O(logn)$。

$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)$。

针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为：$T1(m) + T2(n) = O(f(m) + g(n))$。但是乘法法则继续有效：$T1(m)*T2(n) = O(f(m)* f(n))$。

空间复杂度分析

空间复杂度全称就是渐进空间复杂度（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]
  }
}

跟时间复杂度分析一样，我们可以看到，第 2 行代码中，我们申请了一个空间存储变量 i，但是它是常量阶的，跟数据规模 n 没有关系，所以我们可以忽略。第 3 行申请了一个大小为 n 的 int 类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 $O(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 可能出现在数组的任意位置。如果数组中第一个元素正好是要查找的变量 x，那就不需要继续遍历剩下的 n-1 个数据了，那时间复杂度就是 O(1)。但如果数组中不存在变量 x，那我们就需要把整个数组都遍历一遍，时间复杂度就成了 O(n)。

最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度，同理，最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。

平均情况时间复杂度

我们都知道，最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度，发生的概率其实并不大。为了更好地表示平均情况下的复杂度，我们需要引入另一个概念：平均情况时间复杂度，简称平均时间复杂度。

要查找的变量 x，要么在数组里，要么就不在数组里。这两种情况对应的概率统计起来很麻烦，为了方便你理解，我们假设在数组中与不在数组中的概率都为 1/2。另外，要查找的数据出现在 0 ～ n-1 这 n 个位置的概率也是一样的，为 1/n。所以，根据概率乘法法则，要查找的数据出现在 0 ～ n-1 中任意位置的概率就是 1/(2n)。

所以平均时间复杂度计算过程如下:

$1*\frac{1}{2n}+2*\frac{1}{2n}+3*\frac{1}{3n}+...+n*\frac{1}{2n}+n*\frac{1}{2} = \frac{3n+1}{4}$

这个值就是概率论中的加权平均值，也叫作期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度。

用大 O 表示法来表示，去掉系数和常量，这段代码的加权平均时间复杂度仍然是 O(n)。