数据结构与算法（一）-复杂度分析

发表于 | 分类于 ，

1. 概述

  • 学习算法的复杂度分析的目的
    • 衡量你编写的算法代码的执行效率
    • 让代码运行得更快，如何让代码更省存储空间
  • 复杂度分析的方法
    • 需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法
    • 时间、空间复杂度分析方法

2. 大O表示法

$T(n) = O(f(n))$，其中$T(n)$表示代码执行的时间，n表示数据规模的大小，f(n)表示每行代码执行的次数总和，大O表示T(n)与f(n)成正比。

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

例：

$T(n) = O(2n + 2)$和$T(n) = O(2n^2 + 2n + 3)$用大O表示法表示为$T(n) = O(n)$和$T(n) = O(n^2)$。

3. 时间复杂度分析

  • 原则
    • 只关注循环执行次数最多的一段代码
    • 加法法则：总复杂度等于量级最大的那段代码的复杂度
      • 如果$T1(n) = O(f(n))$，$T2(n) = O(g(n))$，那么$T(n) = T1(n) + T2(n) = max(O(f(n)), O(g(n)) = O(max(f(n), g(n)))$
      • 如果$T1(n) = O(f(n))$，$T2(n) = O(g(n))$，那么$T(n) = T1(n)T2(n) = O(f(n)g(n))$

例1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
 }

单独看 cal() 函数。假设 f() 只是一个普通的操作，那时间复杂度就是，T1(n) = O(n)。但 f() 函数本身不是一个简单的操作，它的时间复杂度是 T2(n) = O(n)，所以，整个 cal() 函数的时间复杂度就是，。

  • 常见时间复杂度
    • 常量阶
      • O(1)
    • 对数阶
      • O(logn)
    • 线性阶
      • O(n)
    • 线性对数阶
      • O(nlogn)
    • 平方阶
      • $O(n^2)$
    • k次方阶
      • $O(n^k)$
    • 指数阶
      • $O(2^n)$
    • 阶乘阶
      • O(n!)

例2：

1
2
3
int i = 8;
int j = 6;
int sum = i + j;

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

例3：

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

变量 i 的取值就是一个等比数列。通过 $2^x = n$，求解$x=log_2n$，所以，这段代码的时间复杂度就是 $O(log_2n)$。把所有对数阶的时间复杂度都记为$O(logn)$。如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。

例4：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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;
}

复杂度是O(m+n)。

4. 空间复杂度分析

渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

例5：

1
2
3
4
5
6
7
8
9
10
11
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)，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。

5. 最好、最坏情况时间复杂度和平均情况时间复杂度

  • 最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度
  • 最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度
  • 平均情况时间复杂度
  • 均摊时间复杂度
    • 均摊时间复杂度就是一种特殊的平均时间复杂度

6. 参考

  • 以上内容为《数据结构与算法之美》学习笔记