北邮研究生课程《算法设计与分析》知识总结 - Part 1

1. 渐近性态#

当$N\to\infty$，忽略低阶项、常数项、常数系数，只保留最高阶主项，用于比较算法效率。 例：$T(N)=3N^2+4N\log N+7$，渐近性态为 $3N^2$，记作 $\Theta(N^2)$。

2. 五大渐近记号#

等价简写（选择/判断常考）

• $f=O(g) \Leftrightarrow f\le g$
• $f=\Omega(g) \Leftrightarrow f\ge g$
• $f=\Theta(g) \Leftrightarrow f=g$
• $f=o(g) \Leftrightarrow f<g$
• $f=\omega(g) \Leftrightarrow f>g$

1. 核心概念#

1. 递归算法：直接/间接调用自身的算法；递归函数：用自身定义的函数。
2. 递归两大必备要素
   • 边界条件（终止条件）：递归出口，保证有限步结束；
   • 递归方程：问题的递推定义。

   易错点：缺少边界条件会造成无限递归。

2. 递归优缺点#

• 优点：逻辑清晰、代码简洁、易理解、便于数学归纳法证明正确性；
• 缺点：调用栈开销大、空间消耗高、调试难度大、运行效率低于非递归。

3. 典型递归函数#

1. 阶乘函数

   $$n! = \begin{cases} 1, & n=0 \\ n\cdot (n-1)!, & n>0 \end{cases}$$

2. Fibonacci 数列

   $$F(n) = \begin{cases} 1, & n=0,1 \\ F(n-1)+F(n-2), & n>1 \end{cases}$$

   朴素递归复杂度：$O(2^n)$（低效，大量重复计算）；最优线性解法 $O(n)$。

3. Ackerman 函数（了解，概念题）

   双递归函数，无法转为非递归形式；增长速度极快，其拟逆函数 $\alpha(n)$ 增长极慢，常规规模下 $\alpha(n)\le4$，常用于复杂度分析。

1. 分治与递归的关系#

分治算法天然适合用递归实现；分治拆解出的子问题和原问题结构一致，是递归的典型应用场景，二者常搭配使用。

2. 分治法适用的4个条件#

1. 问题规模缩小到一定程度后，可直接简单求解；
2. 问题可分解为若干规模更小、同结构的子问题（最优子结构）；
3. 子问题的解可以合并得到原问题的解；
4. 各子问题相互独立，无公共子问题（可并行计算）。

3. 分治法标准三步流程#

1. 分解(Divide)：将原问题划分为 $k$ 个规模均等的子问题（优先均分，提升效率）；
2. 求解(Conquer)：递归求解每个子问题，子问题足够小时直接求解；
3. 合并(Merge)：将所有子问题的解整合，得到原问题解。

4. 分治算法通用递归复杂度公式#

设：问题规模 $n$，分解为 $k$ 个子问题、每个子问题规模 $n/m$，分解+合并总耗时 $f(n)$

5. $m、k$ 对复杂度的影响#

1. $m<k$：子问题总规模 > 原问题，复杂度偏高（例：Strassen 原始矩阵乘法）；
2. $m=k$：子问题总规模 = 原问题，复杂度适中（例：归并排序）；
3. $m>k$：子问题总规模 < 原问题，复杂度最优（例：二分搜索）。

6. 分治 vs 减治法#

• 分治法：分解后需要求解多个子问题，再合并所有解（归并排序、最近点对）；
• 减治法：分解后仅需求解一个子问题，无需复杂合并（二分搜索、线性时间选择）。

（一）二分搜索#

1. 问题前提：有序数组，查找指定元素；
2. 核心思路：每次取中间元素比较，舍去一半区间，仅递归处理一个子区间；
3. 递归复杂度：

4. 复杂度结果：最坏/平均/最好：$O(\log n)$；
5. 应用：红黑树、B/B+树、数据库、操作系统调度。

（二）大整数乘法#

用于超长大整数相乘，分治核心：拆分数字 + 减少乘法次数

1. 普通分治（4次乘法）

   $X = a \cdot 2^{\frac{n}{2}} + b$

   $Y = c \cdot 2^{\frac{n}{2}} + d$

   $XY = ac \cdot 2^n + (bc + ad) \cdot 2^{\frac{n}{2}} + bd$

   递归式：$T(n)=4T(n/2)+O(n)$，复杂度 $O(n^2)$，无优化；

2. 优化分治（3次乘法）

   $$\begin{aligned} XY &= ac \cdot 2^n + (bc + ad) \cdot 2^{\frac{n}{2}} + bd \\ &= ac \cdot 2^n + (bc + ad + ac - ac + bd - bd) \cdot 2^{\frac{n}{2}} + bd \\ &= ac \cdot 2^n + \big((bc + ad - ac - bd) + ac + bd\big) \cdot 2^{\frac{n}{2}} + bd \\ &= {\color{red} ac} \cdot 2^n + \big({\color{green} (a - b)(d - c)} + {\color{red} ac} + {\color{blue} bd}\big) \cdot 2^{\frac{n}{2}} + {\color{blue} bd} \end{aligned}$$

   变形公式减少1次乘法，递归式：$T(n)=3T(n/2)+O(n)$ 复杂度：$\boldsymbol{O(n^{\log_2 3}) \approx O(n^{1.59})}$，效率提升。

示例

这里以计算 $1234 \times 5678$ 为例，展示如何利用优化分治（仅需 3 次乘法）来高效完成大整数乘法。

设基数 $B = 10$，总位数 $n = 4$，半长 $m = \frac{n}{2} = 2$。 将两个数按高位和低位拆分：

• $X = 1234 = {\color{red} 12} \cdot 10^2 + {\color{blue} 34} \implies a = 12,\ b = 34$
• $Y = 5678 = {\color{red} 56} \cdot 10^2 + {\color{blue} 78} \implies c = 56,\ d = 78$

根据变形公式，我们只需要计算以下三个乘积：

利用 $P_1, P_2, P_3$ 还原出中间项 $(bc + ad)$：

(注：传统算法中 $bc + ad = 34 \times 56 + 12 \times 78 = 1904 + 936 = 2840$，结果一致)

将三部分按权重组合：

（三）Strassen 矩阵乘法#

1. 普通矩阵乘法：$n$ 阶矩阵，$O(n^3)$；
2. 标准分块矩阵乘法：8次子矩阵乘法，$T(n)=8T(n/2)+O(n^2)$，仍为 $O(n^3)$；
3. Strassen 优化（7次乘法） 构造7个中间矩阵，减少乘法次数； 递归式：$T(n)=7T(n/2)+O(n^2)$ 复杂度：$\boldsymbol{O(n^{\log_2 7})\approx O(n^{2.81})}$；
4. 特点：大规模矩阵优势明显，小规模常数开销大。

（四）合并排序#

1. 流程：分解→递归排序左右子数组→合并两个有序数组；
2. 合并操作：线性时间 $O(n)$；
3. 递归式：

4. 复杂度：最好/最坏/平均均为 $O(n\log n)$；
5. 空间复杂度：$O(n)$（需要辅助数组）；
6. 特点：分解简单、合并复杂；属于最优排序算法（排序下界 $\Omega(n\log n)$）。

（五）快速排序#

1. 流程：划分(Paitition) → 递归排序左右子区间；无需合并； 划分规则：选基准元素，左小右大。
2. 复杂度分三种情况（必背）
   • 最好情况：划分均衡（基准为中位数），递归式 $T(n)=2T(n/2)+O(n)$，$O(n\log n)$；
   • 最坏情况：划分极度不平衡（有序/逆序数组，基准为最值），递归式 $T(n)=T(n-1)+O(n)$，$\boldsymbol{O(n^2)}$；
   • 平均情况：随机输入，$\boldsymbol{\Theta(n\log n)}$；
3. 优化方案
   • 随机选择基准元素（RandomizedPartition），降低最坏情况概率；
   • 提前判断数组是否已有序，跳过无效划分。
4. 特点：原地排序、辅助空间小；不稳定排序。

（六）线性时间选择（求第k小元素）#

问题：在无序数组中找第 $k$ 小元素（包含最值、中位数）

1. 随机选择版本

   • 思路：借鉴快排划分，只递归处理目标所在单侧子区间；
   • 平均复杂度：$O(n)$；最坏复杂度：$O(n^2)$。

2. 最坏线性时间版本 [BFPTR算法]

   基准选取规则：

   1. 数组按每5个元素分组；
   2. 每组取中位数；
   3. 递归求中位数的中位数作为划分基准；
      • 保证划分后子区间长度不超过原长度的 $3n/4$；
      • 递归式：$T(n)\le T(9n/10)+T(n/5)+O(n)$，最终复杂度 最坏 $O(n)$。

（七）平面最接近点对（分治经典应用题）#

1. 一维情况：数轴上找点对，分治+合并，复杂度 $O(n\log n)$；
2. 二维平面情况（核心） 步骤：
   1. 按 x 坐标中位数分割平面为左右两部分；
   2. 递归求左右区域最小距离 $d_1、d_2$，令 $d=\min(d_1,d_2)$；
   3. 只检查分割线左右距离不超过 $d$ 的点（候选点）；
   4. 利用鸽巢原理：每个点最多只需对比 7 个点，合并步骤线性 $O(n)$；
3. 总递归式：$T(n)=2T(n/2)+O(n)$，复杂度 $\boldsymbol{O(n\log n)}$。

1. 核心思想#

动态规划（DP）用于多阶段最优化问题；将大问题拆分为子问题，记录子问题答案、避免重复计算，以空间换时间，把指数复杂度降为多项式复杂度。

2. 两大必备性质#

1. 最优子结构：原问题的最优解，一定包含其子问题的最优解（DP前提）。
2. 重叠子问题：递归过程中同一个子问题会被多次计算，DP通过表格存储结果，每个子问题只算一次。

3. 动态规划标准四步设计流程#

1. 分析最优解结构，验证最优子结构；
2. 定义状态，递归写出最优值递推公式；
3. 自底向上计算所有子问题最优值；
4. 根据记录表回溯，构造完整最优解。

4. 两种实现方式#

1. 自底向上DP：常规写法，遍历填表，效率高、主流考点；
2. 备忘录方法（自顶向下）：递归+缓存，控制逻辑和纯递归一致，仅重复子问题查表，适合直观理解。

（一）矩阵连乘问题#

1. 问题描述

给定 $n$ 个可连乘矩阵 $A_1A_2\cdots A_n$，矩阵乘法满足结合律，求最优加括号顺序，使得总的数乘次数最少。 设矩阵 $A_i$ 维度：$p_{i-1} \times p_i$。

2. 状态定义

$m[i,j]$：矩阵子链 $A_i \sim A_j$ 的最少数乘次数； $s[i,j]$：记录 $A_i \sim A_j$ 的最优分割位置（用于回溯构造解）。

3. 递推公式

4. 复杂度

• 时间：$O(n^3)$（三层循环）
• 空间：$O(n^2)$（二维状态表）

5. 关键考点

• 穷举/分治解法是指数复杂度，DP优化为多项式复杂度；
• 根据 $s[i,j]$ 回溯输出最终加括号方案；
• 手算填表。

代码见 matrix_chain_multiplication.py

（二）最长公共子序列 LCS#

1. 基本概念

子序列：元素顺序不变，但可不连续； 公共子序列：同时属于两个序列的子序列，求长度最长的一个。

2. 状态定义 $c[i,j]$：序列 $X_1\sim X_i$ 与 $Y_1\sim Y_j$ 的最长公共子序列长度； $b[i,j]$：记录状态转移方向，用于回溯构造LCS。

3. 递推公式

4. 复杂度与优化

• 基础版：时间 $O(mn)$，空间 $O(mn)$（$m、n$ 为两序列长度）；
• 空间优化：仅保留两行数组，空间可降至 $O(\min(m,n))$；
• 可省略方向数组，直接由 $c$ 表回溯。

代码见 longest_common_subsequence.py, LeetCode

（三）最大子段和#

1. 问题描述

给定含正负整数的序列，求连续子数组的最大和；全负数时结果记为0。

2. 状态定义

$b[j]$：以第 $j$ 个元素结尾的最大子段和。

3. 递推公式

$b[j] = \max\big(b[j-1]+a[j],\ a[j]\big)$ 最终答案：$\max\{b[1],b[2],\dots,b[n]\}$

4. 扩展考点

根据DP状态，回溯求出最大子数组的起止下标。

代码见 LeetCode

（四）0-1背包问题#

1. 问题描述
$n$ 件物品，每件重量 $w_i$、价值 $v_i$，背包容量 $C$；每件物品最多选1件，求装入物品的最大总价值。

2. 状态定义
$dp[i][j]$：从前 $i$ 件物品中进行选择，且背包容量为 $j$ 时的最大总价值。
(其中 $1 \le i \le n$，$0 \le j \le C$)

3. 递推公式

边界条件：

• $dp[0][j] = 0 \quad (\forall\ 0 \le j \le C)$，表示没有物品可选时，价值为 0。
• $dp[i][0] = 0 \quad (\forall\ 1 \le i \le n)$，表示背包容量为 0 时，价值为 0。

4. 复杂度与特点

• 时间复杂度：$O(nC)$，需要填充一个 $n \times (C+1)$ 的表格。
• 空间复杂度：基础实现为 $O(nC)$；可优化至 $O(C)$（使用一维数组 $dp[j]$，且内层循环必须逆序遍历 $j$ 从 $C$ 到 $w_i$，以防止物品被重复装入）。
• 算法特点：属于伪多项式时间算法。当背包容量 $C$ 极大（如 $10^9$）而物品总价值较小时，该算法效率会变差（此时可考虑转换状态定义，以“价值”为维度进行 DP）。
• 核心考点：二维表格的填表计算、一维数组的空间优化（及逆序原因）、通过状态表回溯选出具体装入的物品。

（五）流水作业调度（Johnson法则，偏理论+排序应用）#

1. 问题描述

$n$ 个作业依次经过两台机器 $M_1、M_2$ 加工（先$M_1$后$M_2$），$a_i$ 为$M_1$加工时间，$b_i$ 为$M_2$加工时间，求作业顺序，使总完工时间最短。

2. 核心结论：Johnson不等式 & 调度规则

满足 $\min(b_i,a_j) \ge \min(b_j,a_i)$ 的顺序为最优顺序，简化排序规则：

1. 划分两组：

   $N_1=\{i\mid a_i < b_i\}$，$N_2=\{i\mid a_i \ge b_i\}$；

2. $N_1$ 按 $a_i$ 升序排列；

3. $N_2$ 按 $b_i$ 降序排列；

4. 最终顺序：$N_1$ 作业在前，$N_2$ 作业在后。

3. 复杂度

排序为主，时间 $O(n\log n)$，空间 $O(n)$。

1. 贪心算法思想#

每一步只做当前局部最优选择，期望最终得到全局最优；选择一旦确定就不再回溯，执行方式为自顶向下、迭代缩减问题规模。

• 优势：逻辑简单、实现容易、效率高；
• 局限：并非所有问题都能得到全局最优，部分场景仅能求出近似解。
• 反例：特殊硬币找零，贪心选择结果差于全局最优。

2. 适用两大必备性质#

1. 最优子结构：原问题最优解包含子问题最优（贪心、动态规划共同前提）。
2. 贪心选择性质：全局最优可通过一系列局部贪心选择逐步得到（贪心独有关键性质）。

3. 贪心通用框架#

1
解集合S初始为空
2
while 未得到完整可行解:
3
    从候选集中选出局部最优元素x
4
    满足约束则将x加入S
5
    从候选集移除x
6
返回S

4. 贪心 vs 动态规划（高频对比题）#

（一）两类背包对比#

1. 0-1背包

   物品不可分割，只能选/不选；无贪心选择性质，只能用动态规划。

2. 可分割背包（分数背包）

   物品可拆分；贪心策略：优先选择单位重量价值最大的物品。 算法复杂度：主要开销为排序，$O(n\log n)$。

（二）活动安排问题#

1. 问题：选择最多互不冲突的活动（同一时间仅一个活动占用资源）。

2. 最优贪心策略：按结束时间升序排序，每次选最早结束的活动。

   原理：留出更多空闲时间，容纳后续活动。

3. 复杂度：已排序 $O(n)$；未排序需排序，$O(n\log n)$。

4. 最优性证明思路：

   ① 存在包含首个活动的最优解；② 选择后剩余子问题仍最优。

（三）最优装载问题#

1. 问题：轮船限重，装载最多集装箱。
2. 贪心策略：优先装重量最轻的集装箱。
3. 复杂度：排序 $O(n\log n)$。

（四）Dijkstra 单源最短路径 [代码]#

1. 问题：带权非负有向图，求源点到所有顶点的最短路径。
2. 贪心思路：维护已确定最短路径的顶点集合$S$，每次从剩余顶点中选出当前路径最短的点加入$S$，并更新路径长度。
3. 复杂度（邻接矩阵实现）：$O(n^2)$。

（五）哈夫曼编码（最优前缀码）[代码]#

1. 用途：数据压缩，构造最短平均码长的前缀编码。
2. 核心规则：使用最小堆，反复合并两个频率最低的节点，生成哈夫曼树。
3. 关键概念：前缀码（任一编码不是其他编码的前缀）、树总代价 $B(T)=\sum f(c)\cdot d_T(c)$。
4. 复杂度：共$n-1$次合并，堆操作$O(n\log n)$。

（六）最小生成树（MST）#

最小生成树（Minimum Spanning Tree, 简称 MST）是图论中的一个经典问题。它的核心目标是在一个带权重的无向连通图中，找到一棵包含所有顶点的树，使得这棵树的所有边的权重之和最小。

1. MST 性质

设$U$是顶点子集，连接$U$与$V-U$的权值最小边，一定属于某一棵最小生成树（反证法证明）。

2. Prim 算法（基于点的贪心） [代码]

• 思路：从单个顶点出发，每次选取连接树内外权最小的边，逐步扩展生成树。
• 适用：稠密图；邻接矩阵实现 $O(V^2)$，堆优化 $O((V+E)\log V)$。

3. Kruskal 算法（基于边的贪心） [代码]

• 思路：所有边按权升序，依次选边，用并查集判断是否构成环，无环则加入生成树。
• 适用：稀疏图；主要开销为边排序，$O(E\log E)$。

（七）多机调度问题#

1. 问题：$n$个不可中断作业分配到$m$台机器，最小化总完工时间（NP完全问题）。
2. 贪心近似策略：作业按处理时间降序，每次分配给当前负载最小的机器。
3. 复杂度：排序 $O(n\log n)$。

1. 回溯法定义#

回溯法是基于深度优先搜索(DFS) 的系统化穷举算法，核心流程：尝试选择 → 递归深入 → 不满足约束则撤销选择（回溯）； 本质 = 递归遍历 + 状态选择 + 状态撤销，依靠剪枝规避无效搜索，解决组合爆炸问题。

2. 与其他算法区分（选择/判断高频）#

• 对比暴力搜索：回溯增加剪枝，提前终止无效路径，效率远高于纯暴力；
• 对比分治：分治子问题独立、无回溯；回溯子问题关联、需要恢复状态；
• 对比动态规划：DP存储子问题解避免重复计算；回溯不存子问题，靠剪枝优化。

3. 适用场景#

主要解决约束满足问题、组合枚举、最优解搜索：

1. 排列/组合/子集类问题；
2. 棋盘问题（N皇后、数独）；
3. 路径、任务分配等带约束的决策问题。

1. 四步执行流程#

1. 初始化：定义解空间、候选集、约束、路径容器、终止条件；
2. 递归选择：遍历当前所有候选，选中一个并更新状态；
3. 剪枝+终止判断：违反约束直接剪枝；到达叶子则记录有效解；
4. 回溯撤销：移除当前选择、恢复状态，尝试下一个候选。

2. 通用伪代码模板#

1
Backtrack(状态, 路径, 候选集)
2
{
3
    if (到达终止条件) {
4
        记录有效解;
5
        return;
6
    }
7
    for (遍历每一个候选选择)
8
    {
9
        if (违反约束) continue; // 剪枝
10
        选择：加入路径、标记状态
11
        Backtrack(新状态, 新路径, 候选集); // 递归
12
        回溯：移除路径、恢复状态
13
    }
14
}

1. N皇后问题（可行性剪枝代表）#

问题

$N\times N$ 棋盘放置$N$个皇后，任意两个不同行、列、对角线。

约束判定

• 行：按行放置，天然满足；
• 列：标记已占用列；
• 主对角线（行-列 相等）、副对角线（行+列 相等）。

解向量

$x_i$ 表示第$i$行皇后所在列。

复杂度

• 无剪枝：$O(N!)$；
• 剪枝后：远低于$O(N!)$；
• 空间：$O(N)$（路径、标记数组、递归栈）。

2. 组合总和（顺序+数学剪枝结合）#

问题

给定数组，元素可重复选，找出和为target的所有不重复组合。

核心优化

1. 数组排序，为数学剪枝做铺垫；
2. start参数控制遍历起点（顺序剪枝，去重）；
3. 当前和+候选值 > target 直接break（数学剪枝）。

复杂度

最坏 $O(2^k)$（$k$为最大组合长度），剪枝后效率大幅提升；空间 $O(k)$。

3. 子集问题（顺序剪枝）#

问题

求数组所有子集（含空集），子集不重复。

思路

用start保证选取下标严格递增，每进入一层递归就记录当前路径（无需等到叶子）。

复杂度

时间 $O(n\cdot 2^n)$（共$2^n$个子集，每个子集处理$n$）；空间 $O(n)$。

4. 0-1背包（可行性+最优性剪枝）#

问题

物品只能选/不选，背包限重，求最大价值及对应方案。

思路

1. 每个物品二分支：选 / 不选；
2. 可行性剪枝：选中后总重量超容量则截断；
3. 最优性剪枝：当前价值+剩余物品理论最大价值 ≤ 已知最优，直接剪枝。

复杂度

无剪枝 $O(2^n)$；剪枝后可处理中等规模数据；空间 $O(n)$。