算法复杂度分析

事后统计法

事后统计法是指把需要的统计代码跑一遍,通过统计、监控,就能得到算法执行的时间和占用的内存大小。这种统计方法非常有局限性。

事后统计法局限性

  1. 测试结果非常依赖测试环境
  2. 测试结果受数据规模的影响很大

大O复杂度表示法

所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

T(n) = O(f(n))

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

时间复杂度分析

在分析时间复杂度的时候比较实用的方法有下面几个:

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

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

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

几种常见的时间复杂度

常见的时间复杂度从低阶到高阶分别为:

  1. 常量阶:O(1)
  2. 对数阶:O(logn)
  3. 线性阶:O(n)
  4. 线性对数阶:O(nlogn)
  5. 平方阶:O($n^2$)
  6. 指数阶:O($2^n$)
  7. 阶乘阶:O(n!)

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

下面看如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13

// 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;
}
  • 最好情况时间复杂度就是,在最理想的情况下,执行这段代码的时间复杂度,即上面循环只遍历一次就得到结果。
  • 最坏情况时间复杂度就是,在最糟糕的情况下,执行这段代码的时间复杂度,即上面循环把整个数组都遍历一遍

平均情况时间复杂度

  • 平均情况时间复杂度分析,可以先算出该段代码的加权平均值之后再来分析。

均摊时间复杂度

  • 出现O(1)的次数远大于出现O(n)出现的次数,那么平均平摊时间复杂度就是O(1)

空间复杂度

空间复杂度分析可以参考时间复杂度分析。