第一讲 复杂度分析

概要

本文是王争的算法训练营《第一讲 复杂度分析》的学习笔记,分享了时间复杂度的由来,大 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) 。

    原文作者:郑子铭
    原文地址: https://www.cnblogs.com/MingsonZheng/p/16282674.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞