Yu's Exp10RE Space
归档 分类 标签 关于
Yu's Exp10RE Space

目录

目录

算法时间复杂度

 收录于  类别 Algorithm
     约 4063 字   预计阅读 18 分钟    自由转载-非商用-非衍生-保持署名 (CC 4.0 BY-SA)   

每次招聘研发实习生，我都会发现一个现象：不少候选同学对自己所写代码的时间复杂度和空间复杂度说不清楚，哪怕是理工强校或科班出身的同学也不例外。时间和空间复杂度分析作为计算机科学的基本功，还是有必要熟练掌握的。那么，如何正确地分析时间复杂度？又有哪些常见的分析方法和应用场景？下面我们就来聊聊这个话题。

时间复杂度，简单来说，就是一种“粗略”衡量算法执行时间的方式。

代码最终要翻译成计算机指令（如 x86 汇编、Python 虚拟机指令）才能执行。虽然不同指令（加、减、乘、除、比较、赋值等）的实际耗时并不相同，但在复杂度分析中，我们忽略这些常量层面的差异，只关注操作次数的增长量级——这正是大 $O$ 记号（Big O notation）的核心思想。

实际操作时，我们通常会选择一个基本操作（比如比较、赋值、数组访问），统计它执行的次数。对于递归算法，则要通过建立递推关系来求解。

那么，哪些因素会影响算法的操作次数呢？主要有三个：

  • 算法本身的设计。优秀的算法往往能用更少的操作完成任务。
  • 输入数据的规模。绝大多数情况下，数据越多，操作次数越多。
  • 输入数据的分布。即便数据量相同，不同的排列或取值也会影响操作次数。我们常说的最好情况、最坏情况、平均情况时间复杂度，正是由此而来。

因此，在实际开发中，我们通常会根据输入特征（即数据的规模与分布）来选择或设计合适的算法。

了解这些背景之后，接下来我们来看看具体如何分析时间复杂度。

在时间复杂度分析中，我们通常用大 $O$ 记号表示算法的增长趋势。以下是最常见的几种复杂度，按增长速度从慢到快排列：

复杂度 名称 典型场景
$O(1)$ 常数时间 数组按索引访问、哈希表查找
$O(log n)$ 对数时间 二分查找、平衡二叉树的查找
$O(n)$ 线性时间 遍历数组、简单查找
$O(n log n)$ 线性对数时间 快速排序、归并排序等高效排序算法
$O(n^2)$ 平方时间 冒泡排序、选择排序等简单排序算法
$O(2^n)$ 指数时间 递归求解斐波那契数列（未优化）
$O(n!)$ 阶乘时间 全排列问题

需要说明的是，大 $O$ 描述的是最坏情况下的增长趋势，且通常忽略常数因子和低阶项。例如，一个实际执行 $(3n^2 + 5n + 2)$ 次操作的算法，其时间复杂度记为 $O(n^2)$。

分析时间复杂度通常遵循以下步骤：

选择一个最常执行的操作作为计数单位。例如，在循环中常以“比较”、“赋值”或“算术运算”为基本操作。

按代码结构分块分析，最终时间复杂度取增长最快的那一块。常见的结构规则有：

  • 顺序结构：总复杂度 = 各块复杂度之和，取最大值。
  • 条件分支：总复杂度 = 各分支复杂度的最大值（因为最坏情况）。
  • 循环结构：单层循环一般执行次数 × 循环体复杂度；多层循环则为嵌套乘积。

对于递归算法，需要建立递推关系并求解。常见解法包括：

  • 代入法：猜测上界，用数学归纳法证明。
  • 递归树法：画递归树，累加各层代价。
  • 主定理：适用于形如 $T(n) = aT(\frac{n}{b}) + f(n)$ 的递推式，可直接套用公式得到复杂度。

下面通过几个具体代码片段，演示如何分析时间复杂度。

注：arr 数组长度为 $n$。

def get_first(arr):
    return arr[0] if arr else None

无论数组多大，只执行一次数组访问，时间复杂度为 $O(1)$。

def sum_array(arr):
    total = 0
    for x in arr:
        total += x
    return total

循环执行 $n$ 次，每次循环内是常数时间，总复杂度 $O(n)$。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

外层循环 $n$ 次，内层循环平均约 $\frac{n}{2}$ 次，总比较次数约$\frac{n(n-1)}{2}$，因此为$O(n^2)$。

或者直接计算总循环次数：

$$ \sum\limits_{i=0}^{n-1} (n - i - 1) = \sum\limits_{k=0}^{n-1} k = \frac{n(n-1)}{2} $$

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

每次循环将搜索区间缩小一半，最多循环 $⌈log_2 n⌉$次，因此为 $O(log n)$。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

上面的归并排序属于递归算法，我们看下其分治过程：

  1. 分解：将长度为 $n$ 的数组分成两个长度约为 $\frac{n}{2}$ 的子数组。这一步仅需计算中点，时间复杂度为 $O(1)$。
  2. 解决：递归地对两个子数组进行归并排序，每个子数组的排序时间为 $T(\frac{n}{2})$，因此两个子数组总时间为 $2T(\frac{n}{2})$。
  3. 合并：将两个已排序的子数组合并为一个有序数组。合并过程需要遍历两个子数组的所有元素，每个元素比较并移动一次，总操作次数与 $n$ 成正比，即 $O(n)$ 时间。

将上述三部分相加，忽略低阶项和常数因子，即得递推式 $T(n)=2T(\frac{n}{2})+O(n)$，由主定理求解可得 $T(n)=O(nlogn)$。

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

未经优化的递归斐波那契会产生大量重复计算，递推式近似 $T(n)=T(n−1)+T(n−2)+O(1)$，其解为 $O(2^n)$。

随着大模型的兴起，分词算法（Tokenization）成为预处理的关键一环。BPE(Byte-Pair Encoding)是一种经典的子词分词算法，广泛应用于 GPT 等模型。下面我们分析 BPE 训练阶段（即从语料中构建词表）的时间复杂度。

BPE 训练的核心流程如下：

  1. 将语料中的每个单词拆分为字符序列（或字节），并在单词末尾添加特殊结束符。
  2. 统计所有相邻符号对（pair）的出现频次。
  3. 找出频次最高的符号对，将其合并为一个新符号。
  4. 重复步骤 2–3，直到合并次数达到预定词表大小。

设：

  • $N$ 为训练语料的总字符数（或总 token 数）。
  • $V$ 为最终词表大小（即合并次数）。

朴素实现：每次合并后重新扫描全语料统计频次，复杂度为 $O(N \times V)$。当 $N$ 达到数十亿、$V$ 为数万时，该复杂度不可接受。

优化实现（工业界常用方式）：

  • 使用哈希表维护相邻符号对的频次，初始统计一次，复杂度 $O(N)$。
  • 使用最大堆（优先队列）存储符号对及其频次，获取最高频对的时间为 $O(1)$（取堆顶），但维护堆需要 $O(logM)$（$M$ 为不同符号对的数量，$M≤N$）。
  • 合并操作影响局部范围：新符号产生时，只有与新符号相邻的符号对频次会发生变化。因此无需重新扫描全语料，只需更新受影响的符号对频次，并在堆中更新这些对。

这样，总时间复杂度为：

  • 初始统计：$O(N)$。
  • 每次合并：更新局部符号对，每次更新涉及常数个相邻对，每个更新需 $O(logM)$ 调整堆。共 $V$次合并。
  • 总复杂度约为 $O(N+VlogM)$，其中 $M≤N$。

由于 $V≪N$（通常 $V$ 为几万，$N$ 为数十亿），实际运行时 $VlogM$ 远小于 $N$，因此主要瓶颈在于初始扫描和内存访问，整体可近似为 $O(N)$。

BPE 的线性训练复杂度使其能够高效处理海量语料，这也是大模型能够在 TB 级数据上训练分词器的关键。理解这一复杂度，有助于在自定义词表时合理估算资源消耗，并对训练代码的优化方向（如并发、IO）建立正确预期。

Transformer 是大模型的核心架构，其关键组件——自注意力（Self-Attention）——的计算复杂度直接影响模型的训练和推理效率。下面我们分析标准自注意力机制的时间复杂度，并简要介绍优化方向。

给定输入序列长度为 $L$，每个位置的向量维度为 $d$（即输入矩阵 $X \in \mathbb{R}^{L \times d}$）。自注意力计算分为三步：

  1. 线性投影：计算 $Q = XW_Q$、$K = XW_K$、$V = XW_V$，其中 $W_Q, W_K, W_V \in \mathbb{R}^{d \times d}$。
  2. 注意力分数：计算 $S = QK^T$，并缩放 $\frac{S}{\sqrt{d}}$。
  3. 加权求和：对 $S$ 的行应用 softmax，得到注意力矩阵 $A \in \mathbb{R}^{L \times L}$，然后计算 $O = AV$。

我们逐步骤分析基本操作次数（以浮点乘加运算为单位）：

  • 线性投影：$Q, K, V$ 的计算各需 $L \cdot d \cdot d$ 次乘加，即 $3L d^2$。复杂度 $O(L d^2)$。
  • 注意力分数：$QK^T$ 的矩阵乘法维度为 $(L \times d) \times (d \times L)$，计算量为 $L \cdot L \cdot d = L^2 d$。复杂度 $O(L^2 d)$。
  • 加权求和：$AV$ 的矩阵乘法维度为 $(L \times L) \times (L \times d)$，计算量为 $L \cdot L \cdot d = L^2 d$。复杂度 $O(L^2 d)$。
  • softmax 与缩放：对 $S$ 的每个元素进行指数和归一化，计算量为 $O(L^2)$，低于 $L^2 d$（通常 $d$ 较大，如 64~128）。

因此，标准自注意力的总时间复杂度为： $$ O(L d^2 + L^2 d) $$

  • 当 $d$ 较大（如 $d \geq L$）：$L d^2$ 占主导，即 $O(L d^2)$。常见于小序列长度、大模型宽度的场景（如早期 BERT 的 $L=512, d=768$）。
  • 当 $L$ 较大（如 $L \gg d$）：$L^2 d$ 占主导，即 $O(L^2 d)$。常见于长文本处理（如文档摘要、代码生成），当 $L$ 达到数千甚至数万时，$L^2 d$ 成为主要瓶颈。

为降低自注意力的二次复杂度，工业界提出了多种优化方法：

优化技术 核心思想 时间复杂度
稀疏注意力 限制每个 token 只关注局部窗口或少量位置 $O(L \cdot w)$，$w$ 为窗口大小
线性注意力 利用矩阵乘法结合律，将 $QK^T V$ 重排为 $Q(K^T V)$ $O(L d^2)$，消除 $L^2$ 项
FlashAttention 通过分块和算子融合，避免显存中存储完整 $A$ 理论仍是 $O(L^2 d)$，但实际速度提升 2~4 倍
多查询/分组查询注意力 多 head 共享 KV 投影，减少计算量 将 $L d^2$ 中的 $d$ 替换为更小的维度

这些优化使得 Transformer 能够扩展到百万级别长度的序列（如长文档、视频、基因组数据），体现了复杂度分析在指导算法优化中的价值。

理解自注意力的时间复杂度，可以帮助工程师：

  • 预估模型训练/推理的计算和内存需求。
  • 根据业务场景（短文本 vs 长文本）选择合适的注意力变体。
  • 在资源受限环境下做出合理的架构取舍（如减少层数、降低 head 维度等）。

掌握时间复杂度分析，不仅有助于写出高效的代码，也是面试和工程实践中的基本功。最后几条实用建议供参考：

  • 先写对，再优化。不要过早陷入微优化，除非已明确瓶颈。
  • 习惯性思考最坏情况。除非业务场景明确，否则默认分析最坏情况。
  • 多练习。拿自己写的代码练手，问一句“这段代码的时间复杂度是多少？”
  • 善用工具。对复杂算法，可以借助递归树、主定理等方法系统分析。

时间和空间复杂度往往是根据需求权衡的（如缓存提速但占用更多内存），但掌握它们能帮助我们做出更明智的设计决策。希望本文能为大家提供一些帮助。

更新于 2026-03-27
自由转载-非商用-非衍生-保持署名 (CC 4.0 BY-SA)
 Algorithm
 | 主页