数据结构与算法

Appearance

第 2 章 算法复杂度 ​

2.1 为什么要学习算法复杂度 ​

在数据结构与算法的学习过程中，人们往往首先关注下列问题：

  • 这段程序能不能运行？
  • 能不能得到正确答案？
  • 代码写出来是不是够短？

这些问题固然重要，但并不足以用来评价一个算法的优劣。随着输入规模增大，两段都能够正确运行的程序，可能表现出截然不同的效率。

例如，下面两个函数都能判断列表中是否有重复元素：

python
def has_duplicate_v1(arr):
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] == arr[j]:
                return True
    return False
python
def has_duplicate_v2(arr):
    seen = set()
    for x in arr:
        if x in seen:
            return True
        seen.add(x)
    return False

从功能上看，这两个函数完成的是同一项任务；但当数据规模增大时，第一种写法可能迅速变慢，而第二种通常更为高效。这说明，算法的优劣不仅取决于“能否得到正确结果”，还取决于“代价如何随规模增长”。

这正是算法复杂度分析所要回答的核心问题。

算法复杂度研究的不是程序某一次运行耗费了多少秒，而是当输入规模不断增大时，算法所需时间与空间将呈现怎样的增长规律。它帮助我们回答以下更具普遍性的问题：

  • 两个都正确的算法，哪个更适合大规模数据？
  • 一个算法慢，是因为实现细节不好，还是因为思路本身就低效？
  • 在内存有限的设备上，哪种写法更合适？
  • 当 AI 生成多种代码方案时，怎样判断哪一种更优？

因此，复杂度分析并非附属内容，而是理解算法、比较算法以及审查程序质量的重要工具。

2.2 输入规模与增长趋势 ​

在讨论复杂度之前，首先需要明确什么是输入规模。

许多复杂度结论写成 O(n)、O(log n)、O(n^2)。其中的 n 并不是一个固定含义的符号，而是用来表示“问题规模”。

不同问题中，n 的含义不同：

  • 对列表问题，n 可以表示列表长度
  • 对字符串问题，n 可以表示字符串长度
  • 对树问题，n 可以表示结点数
  • 对图问题，n 常表示顶点数，m 表示边数

例如：

  • 在“遍历数组求和”中，n 是数组中元素个数
  • 在“二分查找”中，n 是有序数组的长度
  • 在“归并排序”中，n 是待排序元素个数

只有先明确 n 的含义，复杂度讨论才具有确定的对象。

复杂度分析关注的是增长趋势。设某算法的运行步数大致为：

text
5n + 3

另一个算法运行步数大致是：

text
n^2 + 10n + 7

当 n 较小时，它们之间的差距未必明显；但随着 n 增大，平方项的增长速度会显著快于一次项。复杂度分析所关心的，正是这种“问题规模扩大之后，何者增长更快”的结构性差异。

2.3 Big O 记号 ​

为了刻画增长趋势，算法分析中通常使用 Big O 记号。

如果一个算法在输入规模为 n 时，运行代价随着 n 增长，大致不超过某个函数 f(n) 的数量级，就记作：

text
O(f(n))

在初学阶段，可以将 Big O 理解为：

当 n 足够大时，算法增长速度主要由最高阶的那部分决定。

例如：

  • 5n + 3 记作 O(n)
  • 2n^2 + 7n + 1 记作 O(n^2)
  • 3log n + 8 记作 O(log n)

这说明 Big O 主要忽略以下两类因素：

  • 常数因子
  • 低阶项

因此，Big O 并不告诉我们程序精确运行了多少秒，而是刻画：当问题规模增大时，算法的增长趋势属于何种数量级。

2.3.1 Big O 不是精确时间 ​

某个函数在一台计算机上运行了 0.01 秒，并不能据此断言它的复杂度一定更优，因为实际运行时间还会受到以下因素影响：

  • 机器性能
  • 编程语言
  • 编译器或解释器实现
  • 测试数据分布
  • 常数因子

复杂度分析的目的，正是在于剥离这些偶然因素，提炼出更稳定的结构性结论。

2.3.2 常见复杂度的大小关系 ​

在本章中，最常见的复杂度从低到高大致可排列为：

text
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n)

这一顺序十分重要，它提供了复杂度比较的基本尺度：

  • 常数和对数级通常较快
  • 线性级是很多算法的“基准水平”
  • O(n log n) 往往已经是高效排序算法的典型级别
  • 平方级在数据规模稍大时就可能明显变慢
  • 指数级通常只适合很小规模的问题

需要注意的是，这里比较的只是增长趋势，并不意味着任意一个 O(n) 算法都必然快于任意一个 O(n log n) 算法。在实际规模较小时，常数因子和实现细节仍可能显著影响实际表现。

2.4 时间复杂度 ​

时间复杂度描述的是：当输入规模 n 增长时，算法执行所需步骤数将如何增长。

这里的“步骤数”不必理解为 CPU 的真实指令条数，而可以理解为程序中主要操作的执行次数。

2.4.1 例：顺序查找 ​

python
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

当目标元素位于第一个位置时，只需一次比较即可返回。

当目标元素位于最后一个位置，或目标根本不存在时，算法需要扫描完整个数组。

因此：

  • 最好情况：O(1)
  • 最坏情况：O(n)

若无特别说明，许多教材在给出“该算法的时间复杂度是 O(n)”这类表述时，通常默认指的是最坏情况时间复杂度。

2.4.2 例：二分查找 ​

python
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

二分查找在每一步都将搜索区间缩小一半，因此其执行次数并不是与 n 成正比增长，而是取决于“区间能够被连续对半缩小多少次”。

这类增长趋势记作：

text
O(log n)

这种增长速度低于 O(n)。这也说明“有序”这一前提的重要性：一旦数据有序，许多查找问题便可以从线性级下降到对数级。

2.5 常见时间复杂度及其来源 ​

2.5.1 O(1)：常数级 ​

若某个操作的执行次数不随输入规模变化，则称其为常数级。

例如：

python
first = arr[0]
last = arr[-1]

无论数组有 10 个元素还是 10 万个元素，取首元素和尾元素所需的步骤数都不随 n 增长，因此可视为 O(1)。

2.5.2 O(n)：线性级 ​

如果算法需要将输入整体扫描一遍，则其复杂度通常表现为线性级。

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

循环次数与数组长度成正比，所以时间复杂度是 O(n)。

2.5.3 O(n^2)：平方级 ​

平方级通常来源于双重嵌套循环。

python
def print_pairs(arr):
    for x in arr:
        for y in arr:
            print(x, y)

外层循环执行 n 次，内层每次又执行 n 次，总次数约为 n × n，因此时间复杂度是 O(n^2)。

2.5.4 O(n log n)：线性对数级 ​

这类复杂度常见于“每一层处理全部元素，而层数为对数级”的算法中，例如归并排序。

归并排序的基本思路是：

  1. 把数组不断对半拆分
  2. 分别排好左右两部分
  3. 再把两部分合并起来

若拆分层数约为 log n，且每一层处理的元素总数约为 n，则总复杂度为：

text
O(n log n)

2.5.5 O(2^n)：指数级 ​

指数级通常意味着算法在持续分叉，并且存在大量重复子问题。

朴素递归版斐波那契数列就是一个典型例子：

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

该算法会反复计算 fib(3)、fib(2) 这类相同子问题，因此运行代价增长极快，通常记作 O(2^n)。

2.6 如何分析循环程序的时间复杂度 ​

对初学者而言，复杂度分析常显得较为抽象。对于循环程序，可以先从以下问题入手：

  1. 循环执行多少次？
  2. 每次循环内部做了什么？
  3. 是否存在嵌套？
  4. 是否调用了本身就不便宜的函数？

2.6.1 顺序结构 ​

python
def example(arr):
    total = 0
    for x in arr:
        total += x
    for x in arr:
        print(x)
    return total

这里包含两个顺序执行的循环：

  • 第一个循环：O(n)
  • 第二个循环：O(n)

因此总复杂度为：

text
O(n) + O(n) = O(n)

2.6.2 嵌套结构 ​

python
def example(arr):
    count = 0
    for i in range(len(arr)):
        for j in range(len(arr)):
            count += 1
    return count

外层循环执行 n 次，内层循环也执行 n 次，因此总复杂度为 O(n^2)。

2.6.3 分支结构 ​

python
def example(arr):
    if len(arr) < 100:
        for x in arr:
            print(x)
    else:
        for x in arr:
            print(x * 2)
    return len(arr)

虽然程序包含 if-else 分支，但一次运行只会进入其中一条路径；由于两条路径的复杂度均为 O(n)，因此整体复杂度仍为 O(n)。

2.6.4 不要忽略函数调用 ​

python
def example(arr):
    arr.sort()
    return arr[0]

该程序表面上只有两行代码，但 arr.sort() 本身并不是常数级操作。分析复杂度时，必须将函数调用的内部代价纳入考虑，而不能仅凭代码行数作出判断。

2.7 空间复杂度 ​

算法分析不仅关注“需要多少时间”，还关注“需要多少空间”。

空间复杂度描述的是：当输入规模 n 增长时，算法运行过程中需要的额外存储空间如何增长。

本书如无特别说明，空间复杂度默认指额外空间复杂度，即不计入输入本身占用的空间，而只考察算法额外申请了多少存储空间。

2.7.1 为什么通常不把输入算进去 ​

例如，一个函数接收列表 arr 作为输入。该列表在算法开始之前已经存在，算法只是利用这一输入继续计算。复杂度分析更关心的是：

  • 是否新建了辅助数组？
  • 是否创建了哈希表、集合或矩阵？
  • 递归是否带来了额外调用栈？

因此，空间复杂度所关注的是“除输入本身之外，算法还额外占用了什么”。

2.7.2 O(1) 额外空间 ​

python
def max_value(arr):
    current_max = arr[0]
    for x in arr:
        if x > current_max:
            current_max = x
    return current_max

该算法虽然遍历了整个数组，但额外只使用了少量变量，且变量个数不随 n 增长，因此空间复杂度为 O(1)。

2.7.3 O(n) 额外空间 ​

python
def copy_positive(arr):
    result = []
    for x in arr:
        if x > 0:
            result.append(x)
    return result

在最坏情况下，所有元素都满足条件，result 的长度与 n 同阶，因此空间复杂度为 O(n)。

2.7.4 原地算法 ​

若一个算法主要在原有数据上直接修改，而不额外开辟与 n 同阶的新存储空间，通常称其为原地算法。

例如：

python
def reverse_in_place(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

该算法直接修改原数组，额外变量的数量固定，因此空间复杂度为 O(1)。

需要注意的是，“空间复杂度更低”并不意味着算法必然更优。原地算法可能会改变原数据，而某些应用场景恰恰要求保留原始输入。因此，在分析算法时，既要考察复杂度，也要考察操作语义。

2.8 Python 中的隐藏成本 ​

在实际编程中，许多复杂度判断错误并非来自整体框架，而是来自被忽略的局部操作。Python 尤其值得注意，因为某些写法表面上十分简洁，但其背后可能隐含复制与额外分配。

2.8.1 sorted(arr) 与 arr.sort() ​

这两种写法都用于排序，时间复杂度通常都可视为 O(n log n)，但在语义和空间行为上并不相同。

python
arr = [3, 1, 4, 1, 5]
b = sorted(arr)

这里：

  • b 是一个新列表
  • arr 保持不变
  • 通常需要额外空间来存放排序后的结果

而下面这种写法：

python
arr = [3, 1, 4, 1, 5]
arr.sort()

这里：

  • 排序结果仍存放在 arr 中
  • 原列表被修改
  • 不再返回一个独立的新结果列表

因此，不能只笼统地说“它们的时间复杂度相近”，还应进一步考察：

  • 是否修改原数据
  • 是否返回新对象
  • 空间代价是否不同

2.8.2 切片不是免费的 ​

python
arr = [1, 2, 3, 4, 5]
b = arr[1:]

arr[1:] 表面上看只是“从第二个元素开始取值”，但实际上 Python 会创建一个新的列表。若切片长度为 k，则该操作的时间与额外空间通常都与 k 成正比。

因此，切片不能默认当成 O(1)。

2.8.3 一个常见误区：递归里反复切片 ​

python
def list_sum(arr):
    if not arr:
        return 0
    return arr[0] + list_sum(arr[1:])

这段代码形式简洁，但至少包含以下两个主要成本来源：

  1. 每次递归都要创建新的切片
  2. 每次递归都会增加一层调用栈

如果输入长度为 n：

  • 调用层数约为 n
  • 第一次复制 n - 1 个元素
  • 第二次复制 n - 2 个元素
  • 依此类推

复制总工作量大约是：

text
(n - 1) + (n - 2) + ... + 1 = O(n^2)

因此，这段代码虽然表面上似乎只是“每层处理一个元素”，但在 Python 中并不高效。

2.8.4 新建列表与原地修改 ​

下面比较两种反转写法：

python
def reverse_new(arr):
    result = []
    for i in range(len(arr) - 1, -1, -1):
        result.append(arr[i])
    return result
python
def reverse_in_place(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

二者的时间复杂度都为 O(n)，但空间语义不同：

  • reverse_new 返回一个新列表，空间复杂度为 O(n)
  • reverse_in_place 直接修改原列表，空间复杂度为 O(1)

这一例子说明，即使时间复杂度相同，算法的空间表现与数据语义也可能显著不同。

2.9 最好情况、最坏情况与平均情况 ​

许多算法的代价不仅与输入规模有关，也与输入分布有关。

以线性查找为例：

python
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

若目标恰好位于第一个位置，则只需一次比较，时间复杂度可视为 O(1)。

若目标位于最后一个位置，或根本不存在，则需要扫描完整个数组，时间复杂度为 O(n)。

因此：

  • 最好情况：输入最有利时的复杂度
  • 最坏情况：输入最不利时的复杂度
  • 平均情况：在某种输入分布假设下，平均代价的复杂度

平均情况分析通常更为复杂，因为它依赖于对输入分布的概率假设。在初学阶段，最坏情况分析往往更常用，也更稳定。

2.10 递归复杂度 ​

递归是算法课程中的关键主题。如果不能分析递归复杂度，后续的树、分治、动态规划等内容就很难获得扎实理解。

分析递归复杂度时，可以先从两个问题出发：

  1. 递归树有多深？
  2. 每一层总共做多少工作？

2.10.1 例：简单递归求和 ​

python
def sum_recursive(arr, i):
    if i == len(arr):
        return 0
    return arr[i] + sum_recursive(arr, i + 1)

该函数在每次递归中仅将索引加 1，而不进行切片，因此：

  • 递归深度约为 n
  • 每层只做 O(1) 工作

由此可得：

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)，来自调用栈

2.10.2 例：递归二分查找 ​

python
def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1

    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

每次递归都会把问题规模减半，因此：

  • 递归深度约为 log n
  • 每层只做常数级工作

所以：

  • 时间复杂度：O(log n)
  • 空间复杂度：O(log n)

若改为迭代版，二分查找的空间复杂度可以降为 O(1)。这再次表明，在相同算法思想下，递归实现与迭代实现的空间表现可能不同。

2.10.3 例：归并排序 ​

归并排序的典型递归结构如下：

python
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)

分析该算法时，可以从“层数”与“每层工作量”两个角度入手：

  • 数组不断对半拆分，因此层数约为 log n
  • 每一层所有子问题加起来，处理的元素总数约为 n

因此，其总时间复杂度为：

text
O(n log n)

该算法的空间复杂度通常为什么写作 O(n)？其原因在于：

  • 递归调用栈本身大约是 O(log n)
  • 但切片和合并过程会创建新列表
  • 这些额外数组的主导规模通常是 O(n)

因此，总的额外空间通常写作：

text
O(n)

2.10.4 例：朴素递归斐波那契 ​

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

这一递归形式容易误导初学者，因为它表面上只有一行递归表达式，但其背后对应的是一棵不断分叉的调用树。

以 fib(5) 为例，其调用关系可以简化表示为：

text
fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   └── fib(1)
│   └── fib(2)
└── fib(3)
    ├── fib(2)
    └── fib(1)

由此可以看到：

  • fib(3) 被重复计算
  • fib(2) 也被重复计算

随着 n 增大，这种重复计算会迅速膨胀，因此时间复杂度可记为：

text
O(2^n)

但其空间复杂度并不是 O(2^n)。原因在于，程序运行时同时保留在调用栈中的，只是一条从根到叶子的活动路径。该路径深度与 n 成正比，因此：

text
空间复杂度 = O(n)

这一例子说明：

  • 时间复杂度和空间复杂度不一定同步增长
  • 分支数很多时，时间可能指数爆炸
  • 即使空间只是线性，时间也可能已经不可接受

2.11 常见误区 ​

2.11.1 把代码行数当复杂度 ​

复杂度取决于执行次数和程序结构，而不取决于代码书写了多少行。两行代码也可能隐藏昂贵操作；几十行代码也可能仍然保持在线性级。

2.11.2 把一次运行时间当复杂度 ​

程序在某台机器上运行较快，并不意味着其复杂度一定更低。复杂度讨论的是输入规模增长时的趋势，而不是一次测试所测得的秒数。

2.11.3 只看时间，不看空间 ​

有些算法的时间复杂度相同，但空间代价差异很大。若计算环境受到内存限制，这种差异可能十分关键。

2.11.4 忽略语言细节 ​

理论分析不能完全脱离实现环境。尤其在 Python 中，切片、字符串拼接以及新建列表等写法都可能引入额外成本。

2.11.5 只背结论，不分析来源 ​

真正重要的并不是记住“某算法是 O(n log n)”，而是能够解释：

  • 为什么层数是 log n
  • 为什么每层工作量是 n
  • 为什么空间不是 O(1)

只有做到这一点，复杂度知识才能迁移到新的问题情境之中。

2.12 AI Coding 时代为什么更要学复杂度 ​

在今天的 AI Coding 环境中，大量代码可以通过自然语言直接生成。这使得“写出代码”本身不再是最稀缺的能力；相反，以下能力变得更为重要：

  • 判断 AI 生成的代码是否高效
  • 比较多个方案的代价差异
  • 发现看起来简洁、实际上低效的写法
  • 把复杂度约束写进提示词

例如，针对“删除重复元素”这个问题，AI 可能给出下面两种写法：

python
def dedup_v1(arr):
    result = []
    for x in arr:
        if x not in result:
            result.append(x)
    return result
python
def dedup_v2(arr):
    seen = set()
    result = []
    for x in arr:
        if x not in seen:
            seen.add(x)
            result.append(x)
    return result

如果缺乏复杂度分析能力，学习者可能只会停留在“两个版本都能工作”的判断上；而一旦进行复杂度审查，就会注意到：

  • x not in result 在列表中查找，可能是 O(n)
  • 外层循环本身又是 O(n)
  • 因此第一种写法整体可能达到 O(n^2)

而第二种写法借助集合，通常可以把查重降到更高效的级别。

因此，在 AI Coding 时代，复杂度分析的重要性并没有下降，反而更加突出。它使学习者能够从“接受输出”转向“判断输出”。

2.13 复杂度分析检查清单 ​

学完本章后，面对任何一段算法代码，都可以先依据下面这份清单进行检查：

  1. 输入规模 n 指的是什么？
  2. 时间复杂度是什么？
  3. 空间复杂度是什么？
  4. 这里的空间复杂度是否指额外空间？
  5. 是否存在最好、最坏、平均情况的区别？
  6. 是否有隐藏成本，如切片、复制、排序、拼接？
  7. 如果是递归，递归深度多大？
  8. 每一层总共做了多少工作？
  9. 算法是否修改原数据？
  10. 如果这段代码由 AI 生成，我最应该怀疑哪一部分？

这份检查清单并不是应试技巧，而是训练算法判断能力的日常工具。

2.14 本章小结 ​

本章建立了算法复杂度分析的基本框架。通过本章的学习，应当把握以下要点：

  • 复杂度分析关注的是输入规模增大时的增长趋势
  • Big O 不是精确秒数，而是数量级描述
  • 时间复杂度看“要做多久”，空间复杂度看“要占多少额外空间”
  • 复杂度分析必须先说清 n 的含义
  • 同一算法可能有最好、最坏、平均情况
  • 递归复杂度要从“递归深度”和“每层工作量”两个角度分析
  • Python 中存在切片、复制、新建列表等隐藏成本
  • 在 AI Coding 时代，复杂度分析是审查代码质量的重要能力

最后需要再次强调：

学习复杂度，并不是为了机械记忆一张 Big O 速查表，而是为了形成一种识别算法代价、比较算法方案的分析能力。

2.15 练习 ​

练习 1 ​

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

python
def f(arr):
    s = 0
    for x in arr:
        s += x
    return s

练习 2 ​

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

python
def f(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            print(arr[i], arr[j])

练习 3 ​

比较 sorted(arr) 和 arr.sort() 在以下三个方面的差别：

  • 是否修改原数据
  • 是否返回新列表
  • 空间语义有什么不同

练习 4 ​

解释为什么下面这段代码在 Python 中通常不是 O(n)：

python
def list_sum(arr):
    if not arr:
        return 0
    return arr[0] + list_sum(arr[1:])

练习 5 ​

说明递归版二分查找为什么时间复杂度是 O(log n)，空间复杂度也是 O(log n)。

练习 6 ​

朴素递归斐波那契为什么时间复杂度是指数级，而空间复杂度只是线性级？请结合调用树解释。

2.16 配套交互演示 ​

本章的主体仍然是可连续阅读的教材正文，交互页面则作为关键概念的增强层。

如果希望帮助学生直观看到“规模减半”和“递归分层”的过程，可以配合下面两个页面使用。

2.16.1 递归二分查找演示 ​

递归二分查找交互式演示新窗口打开

2.16.2 归并排序演示 ​

归并排序交互式演示新窗口打开

面向 AI Coding 时代的数据结构与算法课程

Copyright © littleKing