第一讲 复杂度分析


概要

本文是王争的算法训练营《第一讲 复杂度分析》的学习笔记,分享了时间复杂度的由来,大 O 时间复杂度表示法,几种常见的时间复杂度量级,最好、最坏、平均时间复杂度,均摊时间复杂度和摊还分析,空间复杂度分析等等

目录

  • 时间复杂度的由来
  • 大 O 时间复杂度表示法
  • 几种常见的时间复杂度量级
  • 最好、最坏、平均时间复杂度
  • 均摊时间复杂度和摊还分析
  • 空间复杂度分析

时间复杂度的由来

如何计算下面一段代码的执行效率?

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

有一种方法就是在代码的前后加上时间的统计语句

public int sum(int n){     long startTime = System.currentTimeMillis();     int result = 0;     for (int i = 1; i <= n; i++){         result = result + i;     }     long endTime = System.currentTimeMillis();     long costTime = endTime - startTime;     System.out.println("执行代码花费时间为:" + costTime + "ms");     return result; } 

这种方法有两个问题

  • 依赖机器、测试数据(或数据规模)等测试环境
  • 需要写测试代码,需要真的运行代码测试

有没有更加简单地统计执行效率的方法呢?

时间复杂度分析

  • 不依赖机器、测试数据(或数据规模)等测试环境
  • 不需要写测试代码,需要真的运行代码测试
  • 通过肉眼、读代码、粗略来分析

估算下面一段代码的执行效率

public int sum(int n){     int result = 0; // k1 * unit_time     for (int i = 1; i <= n; i++){ // k2 * unit_time         result = result + i; // k3 * unit_time     }     return result; // // k4 * unit_time } 
  • 程序->编译成->机器指令->CPU执行
  • 机器指令平均执行时间 unit_time

总执行时间 = k1 * unit_time + n * k2 * unit_time + n * k3 * unit_time + k4 * unit_time
= (k1 + k4) * unit_time + n * (k2 + k3) * unit_time

用代码的执行时间来表示执行效率,还是比较繁琐的,比较不方便拿来沟通的

大 O 时间复杂度表示法

什么是大 O 时间复杂度表示法

  • 只表示数据规模 n 很大时候的执行效率
  • 忽略低阶、常量、系数,只保留最高“量级”
  • 表示执行时间随数据规模的增长趋势,而不是具体的执行时间

90 + 6 * n + 7 * n^2 + 8 * n^3 ≈ n^3

大 O 时间复杂度表示法的计算方法

public int sum(int n){     int result = 0; // k1 * unit_time 1次     for (int i = 1; i <= n; i++){ // k2 * unit_time n次         result = result + i; // k3 * unit_time n次     }     return result; // // k4 * unit_time 1次 } 

总执行时间 = k1 * unit_time + n * k2 * unit_time + n * k3 * unit_time + k4 * unit_time
= (k1 + k4) * unit_time + n * (k2 + k3) * unit_time

O(n) 忽略低阶、常量、系数

时间复杂度分析练习

public int f(int n) {     int result = 0; // k1 * unit_time 1次     for (int i = 1; i <= n; i++){ // k2 * unit_time n次         for (int j = 1; j <= n; ++j){ // k3 * unit_time n^2次             result = result + i * j; // k4 * unit_time n^2次         }     }     return result; // // k5 * unit_time 1次 } 

总执行时间 = (k1 + k5) * unit_time + n * k2 * unit_time + n^2 * (k3 + k4) * unit_time

O(n^2) 忽略低阶、常量、系数

实际上,时间复杂度跟执行次数最多的那段代码的执行次数成正比

能不能进行一些优化呢?

result = (1 * 1 + 1 * 2 + ... + 1 * n) + (2 * 1 + 2 * 2 + ... + 2 * n) + ... + (n * 1 + n * 2 + ... + n * n)

计算过程优化为:

result = 1 * (1 + 2 + ... + n) + 2 * (1 + 2 + ... + n) + ... + n * (1 + 2 + ... + n)

然后抽出同样的 (1 + 2 + ... + n) 为 temp,修改代码如下

public int f2(int n) {     int tmp = 0;     for (int i = 1; i <= n; i++){         tmp = tmp + 1;     }     int result = 0;     for (int i = 1; i <= n; i++){         result = result + i * tmp;     }     return result; } 

两端代码完成同样的功能,代码 A 的时间复杂度是 O(n^2) ,代码 B 的时间复杂度是 O(n)。那么,代码 B 的执行效率比代码 A 高。

时间复杂度的比较仅限于功能相同的代码之间,如果两段代码功能都不同,比较时间复杂度就没有意义了

几种常见的时间复杂度量级

  • O(1) 常量级 哈希表上的各种操作
  • O(logn) 对数级 二分查找、平衡二叉查找树、跳表
  • O(n) 线性 数组和链表的遍历、二叉树遍历
  • O(nlogn) 快速排序、归并排序、堆排序
  • O(n^2) 冒泡、插入、选择排序
  • O(2^n)指数级 回溯去穷举算法、比如八皇后问题、斐波那契数列
  • O(n!) 比较少见,求全排列,实际上跟 n^n 同阶

On(logn) 对数级时间复杂度

// 返回第一个比 n 大并且为 2 的 k 次方的数 public int f4(int n) { // k1 * unit_time 1次     int i = 1; // k2 * unit_time 1次     while (i <= n){ // k3 * unit_time ?次         i = i * 2; // k4 * unit_time ?次     }     return i; // // k5 * unit_time 1次 } 

i = 1, 2, 4, 8, ... 2^k = 2^0 、2^1, 2^2, 2^3 ... 2^k

i = 2^k > n 时,while 循环结束

以 2 为底求对数

log2 2^k > log2 n

等于

k > log2 n

k = log2 n O(log2 n)-> 统一为 O(logn)

为什么要把底数省略掉,统一表示为 O(logn) 呢?

我们来看下面这个例子

// 返回第一个比 n 大并且为 3 的 k 次方的数 public int f4(int n) { // k1 * unit_time 1次     int i = 1; // k2 * unit_time 1次     while (i <= n){ // k3 * unit_time ?次         i = i * 3; // k4 * unit_time ?次     }     return i; // // k5 * unit_time 1次 } 

i = 1, 3, 9, 27, ... 3^k = 3^0 、3^1, 3^2, 3^3 ... 3^k

i = 3^k > n 时,while 循环结束

k = log3 n

O(log3 n) = O(log3 2 * log2 n)

常数可以省略,所以统一为 O(logn)

最好、最坏、平均时间复杂度

分析下面这段代码的时间复杂度

public int search(int a[], int n, int target) {     for (int i = 0; i < n; i++) { // ?次         if (a[i] == target) { // ?次             return i; // 1次         }     }     return -1; // 1次 } 

第 2、3 行代码有可能执行了 1 次、2 次、3 次 ... n 次

执行效率并不是稳定的,分情况来看,有的时候很快,有的时候很慢

在不同的情况下,执行效率不同,针对这种情况,如何表示代码的执行效率

类比接口的响应时间,我们选取三个不同统计值来表示这段代码的执行效率:

  • 最好情况下的时间复杂度 O(1),类比接口最小响应时间
  • 最差情况下的时间复杂度 O(n),类比接口最大响应时间
  • 平均情况下的时间复杂度 (1 + 2 + 3 + ... + n)/n = O(n),类比接口平均响应时间

均摊时间复杂度和摊还分析

均摊时间复杂度:一种特殊的平均时间复杂度

public class Demo{     private int n = 10;     private int a[] = new int[n];     private int count = 0;     public void insert(int data){         if (count == n){             int b[] = new int[n * 2];             for (int i = 0; i < n; i++) {                 b[i] = a[i];             }             a = b;             n = n * 2;         }         a[count] = data;         count ++ ;     } } 

在我们不停调用 insert 方法的时候,耗时有一定的规律

Demo demo = new Demo(); demo.insert(1); // O(1) demo.insert(2); // O(1) // ... demo.insert(10); // O(1) demo.insert(11); // O(n) n = 10 demo.insert(12); // O(1) // ... demo.insert(20); // O(1) demo.insert(21); // O(n) n = 20 demo.insert(22); // O(1) // ... demo.insert(40); // O(1) demo.insert(41); // O(n) n = 40 demo.insert(42); // O(1) // ... 

当数据超过数组容量的时候需要申请一个更大的空间,并把原来的数据拷贝到新的数组里面

申请空间不会特别耗时,但是循环拷贝数据比较耗时

我们把耗时比较多的操作,比如插入第 11 个元素的时候,因为需要申请空间,拷贝数据,把它的耗时均摊到耗时比较少的操作上面,均摊到插入第 12 个到第 20 个元素上

经过均摊之后,每个操作的耗时都是 O(1),所以时间复杂度就是 O(1)

总结一下

对某个数据结构进行一组连续的操作,大部分情况下时间复杂度都很低,只有个别情况下时间复杂度比较高,而且,这些操作之间存在前后连贯的时序关系,这个时候,我们就可以将这一组操作放在一块分析,看是否能将耗时多的那次操作的耗时,均摊到其他耗时少的操作上

利用摊还分析法分析得到的平均时间复杂度,我们给它起了一个有区分度的名字:均摊时间复杂度。实际上,均摊时间复杂度就是一种特殊的平均时间复杂度。能够应用摊还分析法分析均摊时间复杂度的代码不多,常见的就是支持动态扩容的一些数据结构

在能够应用均摊时间复杂度分析的场景中,一般均摊(平均)时间复杂度就等于最好时间复杂度

空间复杂度分析

// 反转数组 public void reverse(int a[], int n){     int tmp[] = new int[n];     for (int i = 0; i < n; i++) {         tmp[i] = a[n-i-1];     }     for (int i = 0; i < n; i++) {         a[i] = tmp[i];     } } 

空间复杂度 O(n)

// 反转数组 public void reverse2(int a[], int n){     for (int i = 0; i < n/2; i++) {         int tmp = a[i];         a[i] = a[n-i-1];         a[n-i-1] = tmp;     } } 

空间复杂度 O(1)

  • 空间复杂度 -> 峰值
  • 时间复杂度 -> 累加值

源码

https://github.com/MingsonZheng/algorithm

参考

王争的算法训练营(第5期)
https://www.xzgedu.com

第一讲 复杂度分析

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

欢迎转载、使用、重新发布,但务必保留文章署名 郑子铭 (包含链接: http://www.cnblogs.com/MingsonZheng/ ),不得用于商业目的,基于本文修改后的作品务必以相同的许可发布。

如有任何疑问,请与我联系 (MingsonZheng@outlook.com) 。

发表评论

相关文章