基础：Big O、递归、回溯与动态规划

基础：Big O、递归、回溯与动态规划

在深入数据结构与算法之前，你需要先掌握四个基础概念：衡量效率的 Big O 记号、把问题拆成子问题的递归、带剪枝的穷举式回溯，以及避免重复计算的动态规划。本文件会从第一性原理出发逐一讲清它们。

• 本章其余文件都默认你对这四个概念已经驾轻就熟。如果跳过本文件，后面那些 O(n \log n) 标注、递归树遍历、回溯模板和 DP 状态转移看起来就会像魔法，而不是工程。

为什么要学模式，而不是死记

• LeetCode、NeetCode、HackerRank 上有成千上万道编程题。没人能把它们全记住，硬背本身就是必败的策略。面试官不会从固定题库里挑题，他们会改造、组合、伪装题目。你背下的「两数之和」解法，在面试官抛出一个你从没见过的变体时就帮不上忙了。

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

• 比如这三道题：

  • 「在数组中找出和等于目标值的两个数。」
  • 「找出结合能之和等于某阈值的两个分子。」
  • 「给定一组账户余额，找出两个账户，使它们的合计等于某笔债务。」

• 它们看起来风马牛不相及，其实是同一道题：两数之和（Two Sum）。上下文（数字、分子、账户）根本无关。真正的结构是：在一个集合里找互补数 → 哈希表查询。

• 正因如此，本章教的是通过直觉掌握模式，而不是通过重复背答案。对每个模式，我们会讲清：

  • 问题有什么结构特征会暗示该模式（已排序输入 → 双指针；子数组约束 → 滑动窗口；最优子结构 + 重叠子问题 → DP）。
  • 这个模式为什么有效——背后的数学或逻辑推理，而不只是「它能得到正确答案」。
  • 如何迁移——通过同一核心思路在不同情境下的简单、中等、困难变体来示范。

• 当你真正理解了滑动窗口为什么有效（约束的单调性意味着「扩张/收缩」就够了），你就能把它套用到任何具有这种结构的问题上，哪怕是没见过的题。而如果你只是背下了「无重复字符的最长子串」的代码，题目一变你就卡住了。

• 实用的学习策略：

  1. 学会模式（本章）。
  2. 练习识别伪装过的题目中的模式（每节末尾的 NeetCode 课后题）。
  3. 练习在时间压力下实现它。
  4. 面试中：读题 → 剥掉上下文 → 识别模式 → 实现。

Big O 记号

• 当我们说一个算法「快」或「慢」时，需要一种精确的度量方式。**Big O 记号（Big O notation）**描述的是算法的运行时间（或空间占用）如何随输入规模 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)：它们随规模放大的方式一样。在更快的电脑上常数会变，但放大的规律不变。Big O 捕捉的是问题本身的、与硬件无关的内在难度。

增长率层级

• 从最快到最慢：

• 经验法则：现代计算机每秒大约执行 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} 次操作——太慢了。你需要更好的算法。

如何分析 Big 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)。在循环里对 list 用 in 会得到 O(n^2)，而不是 O(n)。

# 坏：O(n^2) —— 对 list 用 "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)——排序占了主导。

• 均摊复杂度：某些操作偶尔很贵，但平均下来很便宜。动态数组的 append 均摊是 O(1)，因为难得一次 O(n) 的扩容被分摊到了 n 次便宜的 append 上。不要把均摊 O(1) 和最坏情况 O(1) 搞混。

空间复杂度

• 空间复杂度遵循同样的 Big O 规则，只是把度量对象从时间换成内存。

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

• 递归栈：每次递归调用都会占用栈空间。递归 n 层深就用 O(n) 空间，哪怕每次调用本身不再分配内存。这就是为什么对 n 个节点的图做递归 DFS 要用 O(n) 空间。

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

递归

• **递归（recursion）**是指一个函数调用自身来求解同一个问题的更小实例。对于具有递归结构的问题——树、嵌套结构、分治、数学序列——这是最自然的做法。

• 每个递归函数都由两部分组成：

  1. 基本情况（base case）：可以直接求解（无需递归）的最小实例。它负责终止递归。
  2. 递归情况（recursive case）：把问题拆成更小的子问题，递归求解，再合并结果。

示例：阶乘

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

• 每次调用都被压入调用栈（call stack）。栈会一直增长，直到命中基本情况，然后随着每次返回逐层弹回。如果递归太深（例如在 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)  # 本节点再加一层
​

• 这个模式——「对左递归，对右递归，合并」——能解决绝大多数树的问题（见文件 03）。

递归 vs 迭代

• 任何递归算法都可以改写成迭代（用显式栈或循环）。迭代避免了调用栈开销和栈溢出风险。

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

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

• 尾递归（tail recursion）：如果递归调用是函数中的最后一步操作（调用返回后不再做任何事），就称为「尾递归」。有些语言（Scheme、Scala）会优化尾调用，使其使用常数栈空间。Python 不优化尾调用，所以 Python 里的尾递归仍然占 O(n) 栈空间。

常见陷阱

回溯

• **回溯（backtracking）**是一种系统地搜索所有可能解的方法：逐步构造解，并在某个部分解不可能导向有效答案时放弃它。

• 把它想象成走迷宫。在每个岔路口你选一条路；如果走进了死胡同，就退回上一个岔路口换一条路。你不会从头重来——而是**回溯（backtrack）**到最近的决策点。

三个步骤

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

1. 选择（choose）：挑一个候选项来扩展当前的部分解。
2. 探索（explore）：从这个候选项出发，递归地尝试构造完整解。
3. 撤销选择（unchoose）：撤销刚才的选择（回溯），换下一个候选项。

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 皇后）。
• 题目要求找到任意一个合法配置：解数独、迷宫找路。
• 搜索空间很大，但可以剪枝：大多数部分解可以早早被否决，不必完整探索。

剪枝如何让它变快

• 没有剪枝的话，回溯会探索每一种组合——指数级时间。**剪枝（pruning）**能早早砍掉分支：

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 万降到约 4 万。好的剪枝能让指数级算法在中等规模的 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!)。

常见陷阱

动态规划

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

• 当问题具有以下两个性质时，DP 就适用：

  1. 最优子结构（optimal substructure）：最优解可以由子问题的最优解构造出来。
  2. 重叠子问题（overlapping subproblems）：同样的子问题在递归过程中反复出现。

斐波那契的启示

• 朴素的递归斐波那契：

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} 次操作——根本算不出来。

• 加上记忆化（memoisation，自顶向下 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) 空间。

• 用制表法（tabulation，自底向上 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 的分类

• 一维 DP：状态依赖单个下标。例子：爬楼梯、打家劫舍、最大子数组。

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

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

• 背包 DP：状态是一个物品下标和一个容量。例子：0/1 背包、零钱兑换、子集和。

• 位掩码 DP（bitmask DP）：状态中包含一个位掩码，表示哪些元素已被使用。例子：旅行商问题（TSP）、指派问题。状态空间是 O(2^n \cdot n)，在 n \leq 20 时可行。

自顶向下 vs 自底向上

• 面试里，自顶向下通常更快写出。生产环境中一般更偏好自底向上，因为性能更好（没有递归开销、缓存行为更好）。

常见陷阱

把它们串起来

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

  1. Big O 告诉你某个方法是否够快。
  2. 递归把问题拆成子问题。
  3. 回溯是「递归 + 选择 + 撤销」，用于穷举式搜索。
  4. DP 是「递归 + 缓存」，用于在重叠子问题上做优化。

• 当你看到一道新题：

  • 估算输入规模 n。能接受多大的 Big O？
  • 如果暴力是指数级，且题目要求枚举/寻找配置：用回溯（配合剪枝让它实际可行）。
  • 如果暴力是指数级，且题目求最优值或计数，并且能看到重叠子问题：用 DP。
  • 如果问题的结构能把搜索空间砍半：用二分查找或分治。
  • 如果问题在序列上，且对子数组有约束：用滑动窗口或双指针。
  • 如果需要快速查找：用哈希表。

• 本章其余文件会把这些思路应用到具体的数据结构和模式上。