在工程领域中，大量问题是难以达到最优解的，许多问题只是被“差不多”的解决了。问题的难以程度一方面取决于问题本身的性质，另一方面也取决于观测问题的人的只是储备。人的知识越完备，经验越多，分析问题就会越深入，问题就能被解决的更优雅。

——摘录

在前面一篇《DS&A重学日志:[一]浅析数据结构与算法的核心概念》中简单的用个人理解的方式介绍了下复杂度分析和大O复杂度表示法，接下来正式的引入科学的概念及定义。

在引入之前，先想一个问题：如果我们想准确的预估一段代码的运行时间，应该如何操作呢？

  1. 确定运行平台，包括硬件配置、编程语言、系统环境等，因为这些因素都会影响代码的运行效率。
  2. 评估各种计算操作所需要的运行时间，例如加法操作需要1ns, 乘法操作需要10ns,打印操作需要5ns等。
  3. 统计代码滑总所有的计算操作，并将所有的操作和执行时间求和，从而得到运行时间。

但实际上，上述的思路仅适合理论情况下，在实际场景中不合理也不现实，因为算法执行效率本就应该与平台无关，另一方面，我们没法准确的获取每种操作的运行时间。

由于实际测试具有较大的局限性，通常都是通过一些计算来评估算法的效率，也就是统计时间增长趋势，这种估算法的方法被称为：渐进复杂度分析（asymptotic complexity analysis）,简称复杂度分析。

复杂度分析的定义

复杂度分析描述的是随着输入数据大小的增加，算法执行所需时间和空间的增长趋势。可以从三个方面来理解：

  • 时间和空间资源：分别对应时间复杂度（time complexity）和空间复杂度(space complexity)
  • 随着输入数据大小的增加：反映了算法执行效率与输入数据体量之间的关系。
  • 时间和空间的增长趋势：表示复杂度分析关注不是运行时间和占用空间的具体值，而是时间或空间增长的“快慢”

针对事后统计法存在的局限性提出的解决方案, 不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方案，这种方案叫做复杂度分析法，也叫大O复杂度表示法。复杂度分析法又分为：时间复杂度分析、空间复杂度分析

大O复杂度表示法

  • 分类
    • 大O时间复杂度表示法（又称：渐进时间复杂度，简称：时间复杂度）
    • 大O空间复杂度表示法（又称：渐进空间复杂度，简称：空间复杂度）
  • 公式：T(n)=O(f(n))
    • T(n) : 表示代码执行的时间，n表示数据规模的大小
    • fn: 表示每行代码执行次数的总和，这是一个公式，所以用fn表示
    • O: 表示代码执行时间T(n)与f(n)表达式成正比

如：T(n) = 2n * unit_time 、 T(n) = (2n2+2n+3)*unit_time。
fn: 2n / fn: (2n2+2n+3)
T(n) = O(2n) / T(n) = O(2n2+2n+3)

大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随着数据规模增长的变化趋势，故也称为渐进时间复杂度。

如何进行时间复杂度分析？

专业（数学）方法：求出函数渐近上界

首先统计操作数量，然后判断渐近上界。

1
2
3
4
5
6
7
def algorithm(n: int):
    a = 1      # +1
    a = a + 1  # +1
    a = a * 2  # +1
    # 循环 n 次
    for i in range(n):  # +1
        print(0)        # +1

如上述代码，给定一个输入大小为n的函数，设算法的操作数量是一个关于数据大小n的函数，记为T(n),则以上函数的操作数量为：T(n) = 3 + 2n，T(n)是一次函数，说明其运行时间的增长趋势是线性的，因此它的时间复杂度是线性阶。

通常将线性阶的时间复杂度记为O(n),这个数学符号称为大O记号（big-O natation）,表示函数T(n)的渐近上界（asymptotic upper bound）。

由此可见时间复杂度分析本质上是计算“操作数量T(n)”的渐近上界。

公式：T(n)=O(f(n))

  • T(n) : 表示代码执行的时间，n表示数据规模的大小
  • fn: 表示每行代码执行次数的总和，这是一个公式，所以用fn表示
  • O: 表示代码执行时间T(n)与f(n)表达式成正比

由此可见：确定f(n)之后，就可以得到时间复杂度O(f(n)).

实用（估算）方法：大O复杂度表示法

方法一：只关注循环执行次数最多的一段代码

  • 通常会忽略T(n)的常量、低阶、系统、只需要记录一个最大阶的量级就好，这段代码执行次数的n的量级，就是整段要分析代码的时间复杂度。

方法二：加法法则：总复杂度等于量级最大的那段代码的复杂度

  • 抽象成公式则为：如果T1(n)=O(f(n))，T2(n)=O(g(n))；那么T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).

方法三：乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

  • 抽象为公式则为：T1(n)=O(f(n))，T2(n)=O(g(n))；那么T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n)).

示例：

1
2
3
4
5
6
7
8
9
10
def algorithm(n: int):
    a = 1      # +0（技巧 1）
    a = a + n  # +0（技巧 1）
    # +n（技巧 2）
    for i in range(5 * n + 1):
        print(0)
    # +n*n（技巧 3）
    for i in range(2 * n): 
        for j in range(n + 1):
            print(0)

完整统计：T(n) = 2n(n+1) + (5n+1) + 2 = $2n^2 + 7n +3$

偷懒统计： $n^2 + n$

上述代码的时间复杂度为：$O(n^2)$

常见时间复杂度类型

  • 多项式量级：
    • 常量阶O(1)、对数阶O(logn)、线性阶O(n)、线性对数阶O(nlogn)、k次方阶O(n^k)
  • 非多项式量级：
    • 指数阶O(2n) 、 阶乘阶O(n!)
    • 当数据规模n越来越大是，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。

按执行效率从高到低排列常见的有：

$$O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)$$

常数阶 < 对数阶 < 线性阶 < 线性对数阶 < 平方阶 < 指数阶 < 阶乘阶

常数阶O(1)

常数阶的操作数量与输入数据大小n无关，即不随着n的变化而变化。

  • 常量级时间复杂度，并不是指只执行了一行代码；
  • 只要代码的执行时间不随n的增大而增大，这样的代码的时间复杂度就记作O(1)，
  • 只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，起时间复杂度依然是O(1)
1
2
3
4
5
6
7
def constant(n: int) -> int:
    """常数阶"""
    count = 0
    size = 100000
    for _ in range(size):
        count += 1
    return count

线性阶O(n)

线性阶的操作数量相对于输入数据的大小n以线性级别增长，通常出现在单层循环中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def linear(n: int) -> int:
    """线性阶"""
    count = 0
    for _ in range(n):
        count += 1
    return count

def array_traversal(nums: list[int]) -> int:
    """线性阶（遍历数组）"""
    count = 0
    # 循环次数与数组长度成正比
    for num in nums:
        count += 1
    return count

需要注意的是：输入数据大小n需根据输入数据的类型来具体确定。比如在第一个示例中，变量 为输入数据大小；在第二个示例中，数组长度 为数据大小。

平方阶O($n^2$)

平方阶的操作数量相对于输入数据大小n以平方级别增长。通常出现在嵌套循环中，外层循环和内存循环的时间复杂度都为$O(n)$，因此总体的时间复杂度为$O(n^2)$

1
2
3
4
5
6
7
8
def quadratic(n: int) -> int:
    """平方阶"""
    count = 0
    # 循环次数与数据大小 n 成平方关系
    for i in range(n):
        for j in range(n):
            count += 1
    return count

指数阶 $O(2^n)$

在算法中，指数阶常出现于递归函数中。在生物学中的“细胞分裂”也是指数阶增长的典型代表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def exponential(n: int) -> int:
    """指数阶（循环实现）"""
    count = 0
    base = 1
    # 细胞每轮一分为二，形成数列 1, 2, 4, 8, ..., 2^(n-1)
    for _ in range(n):
        for _ in range(base):
            count += 1
        base *= 2
    # count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1
    return count

def exp_recur(n: int) -> int:
    """指数阶（递归实现）"""
    if n == 1:
        return 1
    return exp_recur(n - 1) + exp_recur(n - 1) + 1

指数阶增长速度非常迅速，在穷举法（暴力搜索、回溯等）中比较常见。对于数据规模较大的问题，指数阶是不可接受的，通常需要使用动态规划或贪心算法等来解决。

对数阶$O(log n)$

与指数阶相反，对数阶放映了“每轮缩减到一半”的情况。设输入数据大小为n, 由于每轮缩减到一半，因此循环次数是$log2n$，即$2^n$的反函数。

对数阶也常出现于递归函数和分治策略（一分为多和化繁为简）的算法中。它增长缓慢，是仅次于常数阶的理想的时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
def logarithmic(n: int) -> int:
    """对数阶（循环实现）"""
    count = 0
    while n > 1:
        n = n / 2
        count += 1
    return count

def log_recur(n: int) -> int:
    """对数阶（递归实现）"""
    if n <= 1:
        return 0
    return log_recur(n / 2) + 1

线性对数阶$O(nlogn)$

线性对数阶常出现于嵌套循环中，两层循环的时间复杂度分别为$O(nlogn)$ 和 $O(n)$

主流的排序算法的时间复杂度通常为$O(nlogn)$，如：快速排序、归并排序、堆排序等。

1
2
3
4
5
6
7
8
9
10
def linear_log_recur(n: int) -> int:
    """线性对数阶"""
    if n <= 1:
        return 1
    # 一分为二，子问题的规模减小一半
    count = linear_log_recur(n // 2) + linear_log_recur(n // 2)
    # 当前子问题包含 n 个操作
    for _ in range(n):
        count += 1
    return count

阶乘$O(n!)$

阶乘在算法场景中，通常使用递归实现，在数学场景中，对应“全排列”问题。

1
2
3
4
5
6
7
8
9
def factorial_recur(n: int) -> int:
    """阶乘阶（递归实现）"""
    if n == 0:
        return 1
    count = 0
    # 从 1 个分裂出 n 个
    for _ in range(n):
        count += factorial_recur(n - 1)
    return count
  • 在n较大时是不可接受的。

如何进行空间复杂度分析？

空间复杂度（space complexity）用于衡量算法占用内存空间随着数据量变大时的增长趋势。其实和时间复杂度很类似，只需将“运行时间”替换成“占用内存空间”就好。

算法相关空间

算法在运行过程中使用的内存空间主要包括以下几种。

  • 输入空间：用于存储算法的输入数据。
  • 暂存空间：用于存储算法在运行过程中的变量、对象、函数上下文等数据。
  • 输出空间：用于存储算法的输出数据。

一般情况下，空间复杂度的统计范围是“暂存空间”加上“输出空间”。

暂存空间可以进一步划分为三个部分。

  • 暂存数据：用于保存算法运行过程中的各种常量、变量、对象等。
  • 栈帧空间：用于保存调用函数的上下文数据。系统在每次调用函数时都会在栈顶部创建一个栈帧，函数返回后，栈帧空间会被释放。
  • 指令空间：用于保存编译后的程序指令，在实际统计中通常忽略不计。

在分析一段程序的空间复杂度时，我们通常统计暂存数据、栈帧空间和输出数据三部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Node:
    """类"""
    def __init__(self, x: int):
        self.val: int = x              # 节点值
        self.next: Node | None = None  # 指向下一节点的引用

def function() -> int:
    """函数"""
    # 执行某些操作...
    return 0

def algorithm(n) -> int:  # 输入数据
    A = 0                 # 暂存数据（常量，一般用大写字母表示）
    b = 0                 # 暂存数据（变量）
    node = Node(0)        # 暂存数据（对象）
    c = function()        # 栈帧空间（调用函数）
    return A + b + c      # 输出数据

推算方法

空间复杂度的推算方法与时间复杂度大致相同，只需将统计对象从“操作数量”转为“使用空间大小”即可。

而与时间复杂度不同的是，我们通常只关注最差空间复杂度，这是因为内存空间是一项硬性要求，我们必须要确保在所有输入数据下都有足够的内存空间预留。

一般的最差有两层含义：

  1. 以最差输入数据为准
  2. 以算法运行中的峰值内存为准

另外需要注意，在递归函数中，需要统计栈帧空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def function() -> int:
    # 执行某些操作
    return 0

def loop(n: int):
    """循环的空间复杂度为 O(1)"""
    for _ in range(n):
        function()

def recur(n: int):
    """递归的空间复杂度为 O(n)"""
    if n == 1:
        return
    return recur(n - 1)

函数 loop() 和 recur() 的时间复杂度都为 ，但空间复杂度不同。

  • 函数 loop() 在循环中调用了 次 function() ，每轮中的 function() 都返回并释放了栈帧空间，因此空间复杂度仍为 。
  • 递归函数 recur() 在运行过程中会同时存在 个未返回的 recur() ，从而占用 的栈帧空间。

常见空间复杂度类型

$O(1) < O(log n) < O(n) < O(n²) < O(2ⁿ)$

常数阶 < 对数阶 < 线性阶 < 平方阶 < 指数阶

常数阶O(1)

常数阶常见于数量与输入数据大小 无关的常量、变量、对象。

需要注意的是，在循环中初始化变量或调用函数而占用的内存，在进入下一循环后就会被释放，因此不会累积占用空间，空间复杂度仍为 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def function() -> int:
    """函数"""
    # 执行某些操作
    return 0

def constant(n: int):
    """常数阶"""
    # 常量、变量、对象占用 O(1) 空间
    a = 0
    nums = [0] * 10000
    node = ListNode(0)
    # 循环中的变量占用 O(1) 空间
    for _ in range(n):
        c = 0
    # 循环中的函数占用 O(1) 空间
    for _ in range(n):
        function()

线性阶O(n)

线性阶常见于元素数量与n成正比的数组、链表、栈、队列等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def linear(n: int):
    """线性阶"""
    # 长度为 n 的列表占用 O(n) 空间
    nums = [0] * n
    # 长度为 n 的哈希表占用 O(n) 空间
    hmap = dict[int, str]()
    for i in range(n):
        hmap[i] = str(i)
        
        
def linear_recur(n: int):
    """线性阶（递归实现）"""
    print("递归 n =", n)
    if n == 1:
        return
    linear_recur(n - 1)

平方阶O($n^2$)

平方阶常见于矩阵和图，元素数量与n成平方关系：

1
2
3
4
5
6
7
8
9
10
11
12
def quadratic(n: int):
    """平方阶"""
    # 二维列表占用 O(n^2) 空间
    num_matrix = [[0] * n for _ in range(n)]
    
def quadratic_recur(n: int) -> int:
    """平方阶（递归实现）"""
    if n <= 0:
        return 0
    # 数组 nums 长度为 n, n-1, ..., 2, 1
    nums = [0] * n
    return quadratic_recur(n - 1)

指数阶 $O(2^n)$

指数阶常见于二叉树。

1
2
3
4
5
6
7
8
def build_tree(n: int) -> TreeNode | None:
    """指数阶（建立满二叉树）"""
    if n == 0:
        return None
    root = TreeNode(0)
    root.left = build_tree(n - 1)
    root.right = build_tree(n - 1)
    return root

对数阶$O(log n)$

对数阶常见于分治算法。例如归并排序（输入长度为n 的数组，每轮递归将数组从中点处划分为两半，形成高度为 $(log n)$的递归树，使用$O(log n)$ 栈帧空间。）、数字转化为字符串。

权衡利弊

降低时间复杂度通常需要以提升空间复杂度为代价，反之亦然。我们将牺牲内存空间来提升算法运行速度的思路称为“以空间换时间”，反之，则称为“以时间换空间”。

选择那种思路取决于我们更看中哪个方面。在大多数情况下，时间比空间更宝贵，因此“以空间换时间”通常是更常用的策略。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~

本站由 BluesSen 使用 Stellar 1.33.1 主题创建。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

本站总访问量次