RUOCHI.AI
0%

复杂度分析

Posted on Edited on In Valine:
time and space complexity analysis

Reference from 王争,数据结构与算法之美 极客时间 https://time.geekbang.org/column/article/40036

为什么需要复杂度分析

事后统计的方法有非常大的局限性，我们需要一个不用具体的测试数据就可以粗略地估算算法的执行效率的方法。

  1. 测试结果依赖测试环境
  2. 测试结果依赖数据规模

大O 复杂度表示法

假设每行代码的执行时间都一样，为unit_time。那么所有代码的执行时间T(n)与每行代码的执行次数n成正比。

\[T(n) = O(f(n))\]

  • f(n)表示每行代码执行的次数总和
  • O 表示成正比
  • 大 O 时间复杂度并不具体表示代码的真正执行时间，而是表示代码执行时间随数据规模增长的变化趋势。 也叫渐进时间复杂度。
1
2
3
4
5
6
7
8
9
10
11
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;
    }
  }
}

\[T(n) = (2n^2 + 2n + 3) * unit_time = O(n^2)\]

时间复杂度分析

  1. 只关注循环次数最多的那段代码
  2. 加法法则：总的时间复杂度等于量级最大的那段代码的时间复杂度 \[\begin{equation}\begin{split} & 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))) \end{split} \end{equation}\]
  3. 乘法法则：千淘代码的复杂度等于嵌套内外代码复杂度的乘积 \[\begin{equation}\begin{split} & T1(n)=O(f(n)) \\ & T2(n)=O(g(n)) \\ & T(n)=T1(n)*T2(n)= O(f(n))*O((g(n))) = O(f(n)* g(n)) \end{split} \end{equation}\]

常见的复杂度分析实例

复杂度量级可以粗略分为多项式和非多项式。非多项式只有\(O(2^n)\) 和 \(O(n!)\)。非多项式量级的算法问题叫 NP 问题。

  1. O(1) 指常数量级，不是只执行了一行代码。 
    1
    2
    3
    int i = 8;
    int j = 6;
    int sum = i + j;
  2. O(logn),O(nlogn) 在对数阶时间复杂度表示方法里，我们忽略对数的“底”，统一表示为O(logn). 
    1
    2
    3
    4
    i=1;
    while (i <= n)  {
      i = i * 2;
    }
    所有对数阶的时间复杂度问题都是O(logn),因为根据换底公式有： \[log_3 n = log_3 2 \* log_2 n = O(c*log_2 n)\]
  3. O(m+n),O(m*n) m,n表示两个数据规模，我们无法事先评估m和n谁的数量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则。
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(1),O(n),\(O(n^2)\), 对数阶复杂度很少用到。 

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

最好/最坏 情况时间复杂度

  1. 最理想情况下，O(1) 时间能查找到对应元素
  2. 最糟糕情况下，O(n) 时间能查找到对应元素
1
2
3
4
5
6
7
8
9
10
11
12
// 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 在数组中的位置，有n+1中情况。我们把每种情况下，查找需要遍历的元素个数累加起来，然后再除以n+1，就可以得到需要遍历的元素个数的平均值。同时我们假设，每一种情况出现的概率相等。

\[\frac{1+2+3+\cdots+n+n}{n+1} = \frac{n(n+1)}{2(n+1)}\]

这段代码的平均加权时间复杂度仍然是O(n).

均摊时间复杂度(平摊分析)

  1. 最好的情况，直接插入 O(1)
  2. 最坏的情况，需要先遍历计算sum，再插入 O(n)
  3. 每一次 O(n)的操作，都会跟着n-1次O(1)的操作，我们把耗时多的那次操作均摊到接下来的n-1次操作上，这组连续操作的均摊时间复杂度就是O(1).
  4. 均摊时间复杂度是一种特殊的平均时间复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 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;
}