maths-cs-ai-compendium-zh/chapter 14: data structures and algorithms/00. foundations.md

基础：大O表示法、递归、回溯与动态规划

在深入学习数据结构和算法之前，你需要掌握四个基础概念：衡量效率的大O表示法、将问题分解为子问题的递归、带剪枝的穷举搜索——回溯，以及避免冗余计算的动态规划。本文件从基本原理出发逐一讲解。

• 本章后续文件默认你已经熟悉了这四个概念。如果你跳过本文件，那么后面文件中的 O(n \log n) 标注、递归树遍历、回溯模板和 DP 状态转移对你来说就会像是魔法而非工程。

为什么是模式，而非死记硬背

• LeetCode、NeetCode 和 HackerRank 上有成千上万的编程题。没有人能记住全部，试图这么做是注定失败的策略。面试官不会从固定题库中选题——他们会修改、组合、伪装。背下来的"两数之和"解法，当面试官问你一个从未见过的变体时毫无用处。

• 好消息是：核心模式大约只有 15-20 种（双指针、滑动窗口、BFS/DFS、DP、回溯等）。所有问题，无论表面多新颖，最终都归结为这些模式中的一个或几个组合。面试考的不是你是否见过这道题，而是你是否能剥离上下文——故事、具体数据类型、边界情况——识别出底层的模式。

• 考虑这三个问题：

  • "在数组中找到两个数，使其和等于一个目标值。"
  • "找到两个分子，使其结合能之和等于一个阈值。"
  • "给定一个账户余额列表，找到两个账户的余额之和等于一笔债务。"

• 它们看起来截然不同。但它们是同一个问题：两数之和。上下文（数字、分子、账户）无关紧要。其结构是：在集合中搜索补数 → 哈希表查找。

• 这就是本章通过直觉教授模式而非通过重复教授解题方法的原因。对于每个模式，我们都会解释：

  • 问题中的什么结构特征指示了这个模式（输入已排序 → 双指针；子数组约束 → 滑动窗口；最优子结构 + 重叠子问题 → DP）。
  • 为什么这个模式有效——数学或逻辑推理，而不仅仅是"它能给出正确答案"。
  • 如何适配它——通过展示简单、中等和困难变体，在这些变体中相同的核心思想应用于不同的上下文。

• 当你深入理解为什么滑动窗口有效（约束的单调性意味着扩展/收缩就足够了），你就可以将其应用到任何具有该结构的问题上，即使是未曾见过的问题。当你只是背下了"无重复字符的最长子串"的代码，一旦问题发生变化，你就会束手无策。

• 实践策略：

  1. 学习模式（本章）。
  2. 练习识别模式，在伪装的问题中（每个文件末尾的 NeetCode 练习题）。
  3. 练习实现，在时间压力下。
  4. 面试中：阅读题目 → 剥离上下文 → 识别模式 → 实现。

---

大O表示法

• 当我们说一个算法"快"或"慢"时，需要一种精确的衡量方式。大O表示法描述了随着输入规模 n 的增长，算法的运行时间（或空间使用量）如何增长，忽略了常数因子和低阶项。

• 形式化定义：f(n) = O(g(n)) 意味着存在常数 c > 0 和 $n_0$，使得对所有 n \geq n_0 有 $f(n) \leq c \cdot g(n)$。通俗地说：对于大规模输入，f 的增长速度不超过 $g$。

• 为什么要忽略常数？因为 2n 的算法和 5n 的算法都是 $O(n)$：它们的扩展方式相同。在更快的计算机上，常数会变，但扩展性不会。大O表示法捕捉了问题的内在难度，与硬件无关。

增长率层级

• 从最快到最慢：

大O	名称	示例	n = 10^6 次操作
O(1)	常数级	数组访问、哈希查找	1
O(\log n)	对数级	二分查找	20
O(n)	线性级	线性扫描、单循环	10^6
O(n \log n)	线性对数级	归并排序、高效排序	2 \times 10^7
O(n^2)	平方级	嵌套循环、暴力配对	$10^{12}$（太慢）
O(n^3)	立方级	三层嵌套循环、矩阵乘法	$10^{18}$（实在太慢）
O(2^n)	指数级	所有子集、暴力回溯	$10^{301030}$（不可能）
O(n!)	阶乘级	所有排列	荒谬

• 经验法则：现代计算机每秒执行约 $10^8$–10^9 次简单操作。对于1秒的时间限制：

  • O(n) 适用于 n \leq 10^8
  • O(n \log n) 适用于 n \leq 10^7
  • O(n^2) 适用于 n \leq 10^4
  • O(2^n) 适用于 n \leq 25

• 这张表能立即告诉你当前方法是否足够快。如果 n = 10^5 而你的解法是 $O(n^2)$，那就是 10^{10} 次操作——太慢了。你需要一个更好的算法。

如何分析大O

• 单循环遍历 n 个元素：$O(n)$。

total = 0
for x in arr:   # n 次迭代
    total += x   # 每次迭代 O(1)
# 总计：O(n)

• 嵌套循环：迭代次数相乘。

for i in range(n):       # n 次迭代
    for j in range(n):   # 每次 n 次迭代
        process(i, j)    # O(1)
# 总计：O(n^2)

• 每次减半的循环：$O(\log n)$。每次迭代将问题规模减半，所以需要 \log_2 n 次迭代。

i = n
while i > 0:
    process(i)
    i //= 2
# 总计：O(log n)

• 内循环依赖于外循环的嵌套循环：

for i in range(n):
    for j in range(i):   # j 从 0 到 i-1
        process(i, j)
# 总计：0 + 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n^2)

• 递归：写出递推关系并求解（第13章介绍了主定理）。例如，归并排序：$T(n) = 2T(n/2) + O(n) = O(n \log n)$。

常见陷阱

• 隐藏的循环：Python 中 x in list 是 $O(n)$（线性扫描），但 x in set 是 $O(1)$。在循环中对列表使用 in 会得到 $O(n^2)$，而不是 $O(n)$。

# 不好：O(n^2) — 对列表用 "in" 是 O(n)
for x in arr:
    if x in another_list:
        process(x)

# 好：O(n) — 先转换为 set
another_set = set(another_list)
for x in arr:
    if x in another_set:
        process(x)

• 字符串拼接：Python 中 s += c 每次都会复制整个字符串。在 n 次迭代的循环中：$O(1 + 2 + \cdots + n) = O(n^2)$。

• 排序主导：如果你的算法先排序（$O(n \log n)$）然后做线性扫描（$O(n)$），总复杂度是 $O(n \log n)$——排序占主导。

• 平摊复杂度：某些操作偶尔很昂贵，但平摊下来很便宜。动态数组的追加操作平摊复杂度为 $O(1)$，因为罕见的 O(n) 扩容被分摊到 n 次便宜的追加操作中。不要混淆平摊 O(1) 和最坏情况 $O(1)$。

空间复杂度

• 空间复杂度遵循同样的大O规则，只是应用于内存使用而非时间。

• 原地算法使用 O(1) 额外空间（不计输入）。快速排序是 O(\log n) 空间（递归栈深度）。归并排序是 $O(n)$（合并时使用的临时数组）。

• 递归栈：每次递归调用都会使用栈空间。深度为 n 的递归使用 O(n) 空间，即使每次调用没有分配额外内存。这就是为什么在具有 n 个节点的图上进行递归 DFS 使用 O(n) 空间。

• 面试中，始终同时说明时间和空间复杂度。O(n) 时间、O(n) 空间的解法通常可以接受，但 O(n) 时间、O(1) 空间的解法更好。面试官可能会要求你优化其中一个。

---

递归

• 递归是指函数调用自身来解决同一问题的更小实例。它是处理具有递归结构的问题最自然的方式：树、嵌套数据、分治法和数学序列。

• 每个递归函数都有两部分：

  1. 基本情况：可以直接解决的最小的实例（无需递归）。这是递归停止的条件。
  2. 递归情况：将问题分解为更小的子问题，递归求解，然后合并结果。

示例：阶乘

def factorial(n):
    if n <= 1:        # 基本情况
        return 1
    return n * factorial(n - 1)  # 递归情况

• factorial(4) 的执行过程：

  • factorial(4) 调用 factorial(3)
  • factorial(3) 调用 factorial(2)
  • factorial(2) 调用 factorial(1)
  • factorial(1) 返回 1（基本情况）
  • factorial(2) 返回 2 * 1 = 2
  • factorial(3) 返回 3 * 2 = 6
  • factorial(4) 返回 4 * 6 = 24

• 每次调用都被压入调用栈。栈一直增长直到到达基本情况，然后随着每次调用的返回而展开。如果递归太深（例如 Python 中的 factorial(1000000)），栈会溢出（RecursionError）。Python 的默认递归限制是 1000。

如何以递归方式思考

• 关键的思维转变是：信任递归。在编写递归函数时，假设递归调用已经正确返回了更小子问题的答案。你只需要：

  1. 处理基本情况。
  2. 将问题分解为更小的部分。
  3. 合并结果。

• 你不需要在脑中跟踪每一次递归调用。这就像试图通过在心里执行每次迭代来理解一个循环。相反，验证："如果递归调用给了我更小输入的正确结果，那么我的组合步骤是否给出了完整输入的正确结果？"

示例：链表上的递归

• 递归反转链表：

def reverse(head):
    if not head or not head.next:   # 基本情况：0 或 1 个节点
        return head

    new_head = reverse(head.next)   # 反转剩余部分
    head.next.next = head           # 将下一个节点指回当前节点
    head.next = None                # 当前节点现在成为尾节点
    return new_head

• 信任递归：reverse(head.next) 正确反转了链表的剩余部分并返回新的头节点。我们只需将当前节点附加到末尾。

示例：树上的递归

• 计算二叉树的高度：

def height(root):
    if not root:           # 基本情况：空树高度为 0
        return 0
    left_h = height(root.left)    # 左子树高度
    right_h = height(root.right)  # 右子树高度
    return 1 + max(left_h, right_h)  # 当前节点增加 1 层

• 这种模式——"递归左子树，递归右子树，合并结果"——解决了绝大多数树的问题（见文件03）。

递归 vs 迭代

• 每个递归算法都可以转换为迭代算法（使用显式栈或循环）。迭代避免了调用栈开销和栈溢出风险。

• 何时优先使用递归：问题具有自然的递归结构（树、嵌套数据、分治法）。递归解法更简洁、更易于推理。

• 何时优先使用迭代：递归深度可能非常大（例如，处理包含 10^6 个节点的链表）。迭代解法避免了栈溢出。

• 尾递归：如果递归调用是函数中的最后一个操作（递归调用返回后没有后续工作），则该递归调用是"尾递归"的。某些语言（Scheme、Scala）会将尾调用优化为使用常数栈空间。Python 不优化尾调用，因此 Python 中的尾递归仍然使用 O(n) 栈空间。

常见陷阱

陷阱	示例	修复
缺少基本情况	无限递归 → 栈溢出	始终定义何时停止
基本情况错误	递归分解中的差一错误	用最小的输入测试（0、1、2）
问题规模未减小	f(n) 调用 f(n) 而非 f(n-1)	确保子问题严格更小
冗余计算	斐波那契数列：f(n) = f(n-1) + f(n-2) 以指数级重复计算	使用记忆化（→ DP）
Python 递归限制	factorial(10000) 崩溃	使用 sys.setrecursionlimit 或转为迭代

---

回溯

• 回溯是一种系统地探索所有可能解法的方法，通过逐步构建解并在发现部分解不可能得到有效答案时立即放弃。

• 可以把它想象成走迷宫。在每个岔路口，你选择一条路。如果碰到死胡同，你就回到上一个岔路口尝试不同的路。你不会从头开始——你回溯到最近的一个决策点。

三个步骤

每个回溯算法都遵循相同的模式：

1. 选择：选择一个候选来扩展当前的部分解。
2. 探索：递归地尝试从这个候选构建一个完整的解。
3. 撤销：撤销选择（回溯）并尝试下一个候选。

def backtrack(state, choices, result):
    if is_complete(state):
        result.append(state.copy())
        return

    for choice in choices:
        if is_valid(choice, state):
            state.add(choice)           # 1. 选择
            backtrack(state, choices, result)  # 2. 探索
            state.remove(choice)        # 3. 撤销（回溯）

• 撤销步骤是回溯与普通递归的区别所在。没有它，状态会累积所有选择，你就无法探索替代路径。

何时使用回溯

• 问题要求枚举所有有效配置：所有排列、所有子集、所有有效排列（如 N 皇后）。
• 问题要求寻找任何有效配置：数独求解、迷宫寻路。
• 搜索空间很大但可以剪枝：大多数部分解可以在完全探索之前被提前拒绝。

剪枝如何使其变快

• 没有剪枝时，回溯会探索所有可能的组合——指数级时间。剪枝则提前砍掉分支：

for choice in choices:
    if not is_valid(choice, state):
        continue  # 剪枝：跳过整个子树

    state.add(choice)
    backtrack(state, choices, result)
    state.remove(choice)

• 在 N 皇后问题（文件05）中，在放置皇后之前检查列和对角线冲突，将搜索树从 n^n 剪枝到大约 n! 个候选。对于 $n = 8$，这是 1600 万 → 40,000。好的剪枝使指数级算法在中等规模的 n 下变得可行。

生成所有子集（最简单的回溯）

def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path[:])  # 每个部分解都是一个有效的子集

        for i in range(start, len(nums)):
            path.append(nums[i])        # 选择
            backtrack(i + 1, path)       # 探索（i+1：不允许重复使用）
            path.pop()                   # 撤销

    backtrack(0, [])
    return result

• 对于 [1, 2, 3]，递归树：

  • [] → [1] → [1,2] → [1,2,3]（回溯）→ [1,3]（回溯）→ [2] → [2,3]（回溯）→ [3]

• 树中的每个节点是一次对 backtrack 的调用。每个叶子节点（以及中间节点）产生一个子集。总子集数：$2^n$。

生成所有排列

def permutations(nums):
    result = []

    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return

        for i in range(len(remaining)):
            path.append(remaining[i])                    # 选择
            backtrack(path, remaining[:i] + remaining[i+1:])  # 探索
            path.pop()                                   # 撤销

    backtrack([], nums)
    return result

• 总排列数：$n!$。每个排列需要 O(n) 工作来构造 remaining，所以总复杂度为 $O(n \cdot n!)$。

常见陷阱

陷阱	示例	修复
忘记复制路径	result.append(path) —— 所有条目共享同一个列表	result.append(path[:]) 或 path.copy()
未回溯（撤销）	状态不断增长，后面的候选看到过时的状态	递归调用后始终执行 path.pop() 或 state.remove()
循环起始位置错误	子集中有重复项，或排列中出现了不应有的重复使用	使用 start 参数避免重新访问之前的索引
跳过剪枝	探索明显无效的分支	在递归调用前添加 if not is_valid: continue

---

动态规划

• **动态规划（DP）**是一种优化技术，适用于相同子问题被反复求解的情况。DP 不重复计算，而是每个子问题只解一次并存储结果。

• DP 适用于具有两个性质的问题：

  1. 最优子结构：最优解可以由子问题的最优解构建而成。
  2. 重叠子问题：相同的子问题在递归中多次出现。

斐波那契数列的动机

• 朴素递归斐波那契数列：

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

• 对于 fib(5)，递归树：

  • fib(5) 调用 fib(4) 和 fib(3)
  • fib(4) 调用 fib(3) 和 fib(2)
  • fib(3) 被计算了两次，fib(2) 被计算了三次

• 这是 $O(2^n)$，因为树在每一层都分支，而且大多数分支重复计算相同的值。对于 fib(50)，需要超过 10^{15} 次操作——不可行。

• 使用记忆化（自顶向下 DP）：

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

• 现在 fib(3) 只计算一次，存储起来，后续调用直接查找。总计：O(n) 时间，O(n) 空间。

• 使用制表法（自底向上 DP）：

def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

• 同样 O(n) 时间，但自底向上构建解，无需递归。可以进一步优化到 O(1) 空间，因为每个值只依赖于前两个值。

DP 配方

对于任何 DP 问题，遵循以下步骤：

1. 定义状态：dp[i]（或 dp[i][j]）代表什么？这是最难的一步。状态必须捕获足够的信息以做出最优决策。

2. 写出递推关系：dp[i] 如何与更小的子问题关联？这是转移公式。

3. 确定基本情况：哪些是最小的子问题，可以直接求解？

4. 确定迭代顺序：哪些子问题必须先于哪些子问题求解？自底向上：按照确保依赖关系已解决的顺序迭代。自顶向下：递归会自动处理。

5. 优化空间（可选）：如果 dp[i] 只依赖于前一行或前几个条目，你就不需要完整的表。

示例：思路过程

问题：给定一个正整数数组，求不相邻元素的最大和（打家劫舍）。

第1步——定义状态：dp[i] = 考虑元素 nums[0..i] 的最大和。

第2步——写出递推关系：对于元素 $i$，我们要么：

• 跳过它：dp[i] = dp[i-1]（不含元素 i 的最佳和）。
• 取用它：dp[i] = dp[i-2] + nums[i]（必须跳过元素 $i-1$，然后加上元素 $i$）。

所以：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。

第3步——基本情况：dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])。

第4步——迭代顺序：从左到右（每个状态依赖于前两个状态）。

第5步——空间优化：只需要最后两个值。

def rob(nums):
    if len(nums) == 1:
        return nums[0]

    prev2, prev1 = nums[0], max(nums[0], nums[1])

    for i in range(2, len(nums)):
        curr = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, curr

    return prev1

如何识别 DP 问题

• 问题要求最优值（最小成本、最大利润、最长序列）或计数（方法数）。
• 问题在每一步都有选择（取/跳过、向左/向右、使用这枚硬币与否），并且整体最优答案依赖于子问题的最优答案。
• 画出递归树会显示重复的子问题。
• 暴力解法是指数级的，但不同的状态比递归调用少得多。

DP 的分类

• 1D DP：状态依赖于单个索引。示例：爬楼梯、打家劫舍、最大子数组。

• 2D DP：状态依赖于两个索引。示例：最长公共子序列（dp[i][j] 表示字符串1的前 i 个字符和字符串2的前 j 个字符）、编辑距离、网格路径问题。

• 区间 DP：状态是一个区间 dp[i][j]，表示 arr[i..j] 上的子问题。示例：矩阵链乘法、戳气球。

• 背包 DP：状态是物品索引和容量。示例：0/1 背包、零钱兑换、子集和。

• 位掩码 DP：状态包含一个位掩码，表示哪些元素已被使用。示例：旅行商问题、分配问题。状态空间为 $O(2^n \cdot n)$，对于 n \leq 20 可行。

自顶向下 vs 自底向上

	自顶向下（记忆化）	自底向上（制表法）
实现	递归 + 缓存	迭代 + 表
计算	只计算实际需要的子问题	计算直到目标的所有子问题
栈溢出风险	有（深度递归）	无
空间优化	较难	较易（使用滚动数组）
编码难度	通常更自然（写递归，加缓存）	需要考虑迭代顺序

• 在面试中，自顶向下通常编码更快。在生产环境中，自底向上通常更受青睐（无递归开销，缓存行为更好）。

常见陷阱

陷阱	示例	修复
状态定义错误	dp[i] 没有捕获足够信息来做决策	增加维度（例如用 dp[i][j] 代替 dp[i]）
缺少基本情况	dp[0] 错误 → 所有后续值都错	手动验证基本情况
迭代顺序错误	在依赖关系未解决之前计算 dp[i]	画出依赖箭头并相应迭代
未正确初始化 dp	用 0 而应该用无穷大（求最小值时）	最小化用 float('inf')，最大化用 float('-inf')
忘记考虑"跳过"选项	总是取当前元素	递推关系通常有 max(take, skip)
可变的默认参数	def f(memo={}) 在调用间共享缓存	def f(memo=None): if memo is None: memo = {}
2D DP 中的差一错误	dp 是 1-indexed 时访问 text1[i]	dp 大小为 (m+1) x (n+1)，访问 text1[i-1]

---

融会贯通

• 这四个概念构成一个递进关系：

  1. 大O表示法告诉你一个方法是否足够快。
  2. 递归将问题分解为子问题。
  3. 回溯是递归 + 选择 + 撤销，用于穷举搜索。
  4. DP是递归 + 缓存，用于具有重叠子问题的优化。

• 当你遇到一个新问题时：

  • 估计输入规模 $n$。什么样的 Big O 是可接受的？
  • 如果暴力解法是指数级的，且问题要求枚举/寻找配置：回溯（配合剪枝使其可行）。
  • 如果暴力解法是指数级的，且问题要求最优值或计数，并且你看到重叠子问题：DP。
  • 如果问题具有减半搜索空间的结构：二分查找或分治法。
  • 如果问题涉及序列且有子数组约束：滑动窗口或双指针。
  • 如果问题需要快速查找：哈希表。