第一讲复杂度分析

技术分享 3年前 (2022-05-18) 0 999+

概要

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

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)