『数据结构与算法』—— 复杂度

  |     |   本文总阅读量:

重要性

复杂度分析是整个算法学习的精髓,只要掌握了它,数据结构和算法的内容基本上就掌握了一半。

  1. 测试结果非常依赖测试环境

  2. 测试结果受数据规模的影响很大

我们需要一个不用具体的测试数据来测试,就可以粗略地估计算法的执行效率的方法。

大 O 复杂度表示法

1
2
3
4
5
6
7
8
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}

第 2、3 行代码分别需要 1 个 unit_time 的执行时间,第 4、5 行都运行了 n 遍,所以需要 2nunit_time 的执行时间,所以这段代码总的执行时间就是 (2n+2)unit_time。可以看出来,所有代码的执行时间 T(n) 与每行代码的执行次数成正比。

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

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

这就是大 O 时间复杂度表示法,大 O 时间复杂度实际上并不具体代表代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以也叫做 渐进时间复杂度,简称 时间复杂度

分析时间复杂度

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

    我们在分析一个算法、一段代码的时间复杂度的时候,也只关注循环执行次数最多的那一段代码就可以了。

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

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

时间复杂度实例分析

image-20181030151057149

空间复杂度分析

时间复杂度的全称是 渐进时间复杂度,表示算法的执行时间与数据规模之间的增长关系。类比一下,空间复杂度全称就是渐进空间复杂度,表示算法的存储空间与数据规模之间的增长关系。

复杂度种类

  1. 最好情况时间复杂度

    最好情况时间复杂度就是,在最理想的情况下,执行这段代码的时间复杂度。

  2. 最坏情况时间复杂度

    最坏情况时间复杂度就是,在最糟糕的情况下,执行这段代码的时间复杂度。

  3. 平均情况时间复杂度

  4. 均摊时间复杂度

例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 全局变量,大小为 10 的数组 array,长度 len,下标 i。
int array[] = new int[10];
int len = 10;
int i = 0;

// 往数组中添加一个元素
void add(int element) {
if (i >= len) { // 数组空间不够了
// 重新申请一个 2 倍大小的数组空间
int new_array[] = new int[len*2];
// 把原来 array 数组中的数据依次 copy 到 new_array
for (int j = 0; j < len; ++j) {
new_array[j] = array[j];
}
// new_array 复制给 array,array 现在大小就是 2 倍 len 了
array = new_array;
len = 2 * len;
}
// 将 element 放到下标为 i 的位置,下标 i 加一
array[i] = element;
++i;
}

最好 $O(1)$,最坏 $O(n)$,平均 $O(n)$,均摊 $O(1)$

参考自极客时间


赏我 e(=2.72) 元咖啡钱吧,您的支持将鼓励我继续创作!



文章目录
  1. 1. 重要性
  2. 2. 大 O 复杂度表示法
  3. 3. 分析时间复杂度
  4. 4. 时间复杂度实例分析
  5. 5. 空间复杂度分析
  6. 6. 复杂度种类
您是第 位小伙伴 | 本站总访问量 | 已经写了 91.2k 字啦

载入天数...载入时分秒...