高级算法设计和分析技术

思维导图

常见算法题
常见算法题.xmind

常用数学公式

公式	名称	说明
$\sum\limits_{i=1}^{n}i=\frac{n(n+1)}{2}$	等差数列和	1+2+3+…+n
$\sum\limits_{i=1}^{n}(2i-1)=n^{2}$	奇数和	1+3+5+…+(2n-1)
$\sum\limits_{i=1}^{n}i^{2}=\frac{n(n+1)(2n+1)}{6}$	平方和	$1^{2}+2^{2}+3^{2}+...+n^{2}$
$\sum\limits_{i=1}^{n}i^{3}=\left(\frac{n(n+1)}{2}\right)^{2}$	立方和	等于平方和的平方
$\sum\limits_{i=0}^{n-1}r^{i}=\frac{1-r^{n}}{1-r}$	等比数列和	$r\neq1$
$\sum\limits_{i=0}^{n-1}2^{i}=2^{n}-1$	2的幂和	特殊等比
$\sum\limits_{i=1}^{n}\log i=\log(n!)$	对数和	常用于分析复杂度
$\sum\limits_{i=1}^{n}\frac{1}{i}\approx\ln n+\gamma$	调和级数	$\gamma\approx 0.577$欧拉常数

公式	名称	说明
$n! = \prod_{i=1}^{n} i$	阶乘	$1 \times 2 \times 3 \times ... \times n$
$a^{n} = \prod_{i=1}^{n} a$	幂	a 连乘 n 次
$\prod_{i=0}^{n-1} (x - r_{i})$	多项式因式分解	韦达定理基础
$\prod_{i=1}^{n} i^{i}$	超级阶乘	不常用但有趣

公式	应用场景
$1 + 2 + \dots + k = \frac{k(k + 1)}{2}$	硬币排列问题、判断三角数
$1 + r + r^{2} + \dots = \frac{1}{1 - r}$ (对于 $\mid r \mid < 1$)	概率计算、几何分布
$\log(n!) \approx n\log n - n$	分析快速排序等算法的时间复杂度
$1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} = H_{n} \approx \ln n + \gamma$	分析堆排序中建堆操作的时间复杂度
$2^{0} + 2^{1} + \dots + 2^{n - 1} = 2^{n} - 1$	计算完全二叉树的节点总数、位运算操作

递归树分析法与算法复杂度速查表

算法复杂度总览

算法类别	经典算法	递归树分析（递归实现）	非递归实现	应用场景
基础遍历算法	二叉树前/中/后序	树高 h：O(n)~O(log n) 每层成本 C：O(1) 总复杂度：O(n)	时间复杂度：O(n) 空间复杂度：O(h) 实现：显式栈模拟	树结构访问、序列化
分治算法	归并排序	树高 h：O(log n) 每层成本 C：O(n) 总复杂度：O(n log n)	时间复杂度：O(n log n) 空间复杂度：O(n) 实现：迭代合并子数组	排序、外部排序
	快速排序	树高 h：O(log n)~O(n) 每层成本 C：O(n) 总复杂度：O(n log n)	时间复杂度：O(n log n) 空间复杂度：O(log n) 实现：栈存储子区间边界	内存排序、TopK问题
搜索算法	二分查找	树高 h：O(log n) 每层成本 C：O(1) 总复杂度：O(log n)	时间复杂度：O(log n) 空间复杂度：O(1) 实现：循环更新左右指针	有序数据检索
	DFS（图遍历）	树高 h：O(|V|) 每层成本 C：O(1) 总复杂度：O(|V| + |E|)	时间复杂度：O(|V| + |E|) 空间复杂度：O(|V|) 实现：显式栈存储节点	连通性检测、拓扑排序
	BFS（图遍历）	树高 h：O(|V|) 每层成本 C：O(1) 总复杂度：O(|V| + |E|)	时间复杂度：O(|V| + |E|) 空间复杂度：O(|V|) 实现：队列管理访问顺序	最短路径（未加权图）
DP与高级结构	斐波那契数列	树高 h：O(n) 每层成本 C：O(1) 总复杂度：O(2ⁿ)	时间复杂度：O(n) 空间复杂度：O(1) 实现：滚动数组更新	状态转移、数学问题
	堆排序	树高 h：O(log n) 每层成本 C：O(log n) 总复杂度：O(n log n)	时间复杂度：O(n log n) 空间复杂度：O(1) 实现：循环下沉+交换	优先级队列、流式数据排序
	并查集（路径压缩）	树高 h：O(α(n)) 每层成本 C：O(1) 总复杂度：O(α(n))	时间复杂度：O(α(n)) 空间复杂度：O(n) 实现：迭代路径压缩	连通分量、动态连接问题

Big O 标记代表一个函数的集合。记忆化搜索实际上稍微比DP慢，但是它们仍然在一个集合里，所以可以认为它们时间复杂度一样。

通常我们研究算法的复杂度 big O 记法是研究算法的最坏复杂度，而研究数据结构 API 的复杂度，则研究其平均复杂度，这就是为什么哈希表的API操作经过摊还以后，得到 O(1) 的复杂度。

递归算法的时间复杂度 = 递归的次数 x 函数本身的时间复杂度

递归算法的空间复杂度 = 递归堆栈的深度 + 算法申请的存储空间

或者再说得直观一点：

递归算法的时间复杂度 = 递归树的节点个数 x 每个节点的时间复杂度

递归算法的空间复杂度 = 递归树的高度 + 算法申请的存储空间

非递归算法中嵌套循环的复杂度依然可能是线性的：

而指针移动类的算法时间复杂度往往是两层 while 循环化简为 O(n)-因为内层的循环实际上是重复的时间条件。

递归树分析核心方法论总结

1. 树高（h）确定

• 分治算法：h = 分支数（b）对规模（n）的对数，即 h = log_b n（如归并排序 b=2）
• 遍历算法：h = 数据结构深度（如二叉树高度 O(log n)~O(n)）
• DP/搜索：h = 状态转移步数（如斐波那契 h=n）

2. 每层成本（C）计算

• 固定成本：每节点操作恒定（如二分查找 C=O(1)）
• 线性成本：每层操作数与层规模正比（如归并排序每层合并 O(n)）
• 递减成本：子问题规模逐层衰减（如快排每层分区 O(n) → O(n/2)）

3. 总复杂度公式

$T(n) = \sum_{\text{layer}=0}^{h} C_{\text{layer}}$

• 均匀分层：若每层 $C_{\text{layer}} = O(n)$ 且 $h = O(\log n)$，则 $T(n) = O(n \log n)$（如归并排序）
• 几何级数：若 $C_{\text{layer}} = O(r^k)$（r为衰减比），则总复杂度由首项或末项主导（如快排平均 $O(n \log n)$）

如果将回溯算法的执行过程想象成一棵决策树，我们可以观察到这棵树通常是k叉树的形式，类似于有放回的抽球过程。在这种模型下，k叉树的高度通常等于问题的规模n，因为每个原始问题的元素（或每个决策步骤）都需要进行一次抉择。基于这种简化的模型，算法的时间复杂度上界可以粗略估计为指数级的 O(k^n)。

以换零钱问题为例：假设要兑换11元，且有5种不同面值的货币可供选择。在最简化的情况下，可以将问题建模为：对于需要兑换的总金额（11元），每1元都面临5种货币选择。这样就形成了一个高度为11、分支因子为5的决策树，基于这种粗略模型，时间复杂度的上界估计为 O(5^11) - O(k^n)。

类似的分析方法也适用于其他DFS（深度优先搜索）算法。需要注意的是，这种分析给出的是算法复杂度的上界估计，实际实现中往往存在剪枝、重叠子问题等优化空间，使得实际性能可能远优于这个理论上界。

而一旦引入记忆法，去除了重复问题，所有要解决的问题的数就不是重复分散在树里面了，而可以理解为一个链表，也就是复杂度的算法变成：

  递归的次数 x 函数本身的时间复杂度
= 递归树节点个数 x 每个节点的时间复杂度
= 状态个数 x 计算每个状态的时间复杂度
= 子问题个数 x 解决每个子问题的时间复杂度
= O(N) * O(K)
= O(NK)

dp化不会比记忆化搜索时间复杂度更快，也是O(NK)。

暴力全排列（arrangement）的复杂度是 O(n!)，暴力子集枚举的复杂度是 $O(k^n)$。可以认为000的全二进制组合就是一个典型的“子集枚举”问题-每个元素全部投入成为乘法原理的一部分。

4. 非递归优化关键

• 栈/队列替代：用显式栈避免递归调用栈溢出（如二叉树遍历）
• 尾递归消除：转换为迭代减少空间（如二分查找）
• 迭代DP：自底向上计算避免重复子问题（如斐波那契）

主方法 & 性能思维速记

主方法 Master Method

递推式	条件	结果
$T(n)=aT(n/b)+f(n)$	$f(n)=O(n^{\log_b a-\varepsilon})$	$T(n)=\Theta(n^{\log_b a})$
	$f(n)=\Theta(n^{\log_b a}\log^k n)$	$T(n)=\Theta(n^{\log_b a}\log^{k+1} n)$
	$f(n)=\Omega(n^{\log_b a+\varepsilon})$ 且正则*	$T(n)=\Theta(f(n))$

正则条件：存在常数 $c<1$ 使得对充分大的 $n$ 有 $a f(n/b)\leq c f(n)$。

1.1 三步口诀

1. 算指数 log_b a
2. 把 f(n) 跟它比“大小”
3. 落入 Case 1 / 2 / 3 → 读出答案

常见案例

算法	a	b	f(n)	主方法结果
归并排序	2	2	Θ(n)	Θ(n log n)
快速排序(平均)	2	2	Θ(n)	Θ(n log n)
二叉查找	1	2	Θ(1)	Θ(log n)
线段树查询	2	2	Θ(1)	Θ(log n)

2. 估算 f(n) 的三步诊断法

1. 写骨架伪代码（Split / Work / Merge）
2. 画递归树最后一英里：

叶子总量 vs 上层总量 速查表

3. 微基准钉常数：JMH / 计时器测 c_split, c_merge

口诀：

“先画骨架，再看叶子，最后拿尺子量常数。”

叶子复杂度来源

叶子动作	复杂度	例子
一条指令	Θ(1)	线段树单点访问
线性扫描	Θ(k)	快排小数组插排
继续分治	Θ(k log k)	TimSort 小片段

平摊分析 Amortized Analysis

把一次“天价操作”平摊到整个序列：

总成本 ÷ 操作次数 = 平摊代价

三种套路

• 聚合 T_total / n
• 会计 预付“信用”
• 势能 Φ 函数记账

多项式 vs 非多项式

类别	形式	例子
多项式	$n^k$ (k 常数)	O(n² log n)
非多项式	指数/阶乘/超多项式	O(2ⁿ), O(n!)

性能维度六层面

维度	问题	算法	系统结构	代码	系统软件	硬件
运行时间	问题规模	复杂度	并行	热点优化	JIT	更高主频
可靠性	需求	幂等重试	主备	RAII	看门狗	ECC
安全性	最小权限	加密	网络分区	静态分析	SELinux	TPM

排序算法对比表

算法分类	算法名称	最佳时间复杂度	平均时间复杂度	最差时间复杂度	空间复杂度
遍历排序 O(n²)	选择排序	O(n²)	O(n²)	O(n²)	O(1)
	冒泡排序	O(n)	O(n²)	O(n²)	O(1)
	插入排序	O(n)	O(n²)	O(n²)	O(1)
分治排序	快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)
	归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)
	堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)
线性排序 O(n)	桶排序	O(n + k)	O(n + k)	O(n²)	O(n + k)
	计数排序	O(n + m)	O(n + m)	O(n + m)	O(n + m)
	基数排序	O(n k)	O(n k)	O(n k)	O(n + b)

参数说明

• n: 数据量大小
• k (桶排序): 桶数量
• m (计数排序): 数据范围
• k (基数排序): 最大位数
• b (基数排序): 数据进制

性能评价

指标	评价标准
时间复杂度	优: O(n log n) / O(n) → 中: O(n k) → 差: O(n²)
空间复杂度	优: O(1) → 中: O(log n) / O(n) → 差: O(n + k)

CLRS 算法学习顺序与递进关系

%% CLRS 算法学习顺序与递进关系（包含排序算法详细步骤）
flowchart TD
    subgraph 数学&编程基础
        A[离散数学] --> B[大O/Θ/Ω 记号]
        B --> C[概率基础]
    end

    subgraph 基础数据结构
        C --> D1[数组/链表/栈/队列]
        D1 --> D2[哈希表]
        D2 --> D3[二叉查找树 BST]
        D3 --> D4[红黑树 / AVL]
    end

    subgraph 排序与分治
        D1 --> E1[插入/选择/冒泡排序]
        D1 --> E2[归并排序]
        E2 --> E3[快速排序]
        E2 -.->|可选| E4[随机化快速排序]
        C --> E4
        E1 -.->|提供复杂度对照组| E3
        E1 -.->|展示原地重排细节| E3
        E1 -.->|对比增量 vs 分治| E3

        %% 插入排序详细步骤
        subgraph 插入排序步骤
            IS1[开始：i=1] --> IS2[取出 arr_i 作为 key]
            IS2 --> IS3[j = i-1，向左扫描]
            IS3 --> IS4{arr_j > key?}
            IS4 -->|是| IS5[arr_j+1 = arr_j<br/>j--]
            IS5 --> IS6{j >= 0?}
            IS6 -->|是| IS4
            IS6 -->|否| IS7[arr_j+1 = key]
            IS4 -->|否| IS7
            IS7 --> IS8[i++]
            IS8 --> IS9{i < n?}
            IS9 -->|是| IS2
            IS9 -->|否| IS10[排序完成]
        end

        %% 归并排序详细步骤
        subgraph 归并排序步骤
            MS1[开始：mergeSort arr, 0, n-1] --> MS2{left < right?}
            MS2 -->|否| MS3[返回]
            MS2 -->|是| MS4[mid = left+right/2]
            MS4 --> MS5[递归：mergeSort arr, left, mid]
            MS5 --> MS6[递归：mergeSort arr, mid+1, right]
            MS6 --> MS7[merge arr, left, mid, right]
            MS7 --> MS8[创建临时数组 L, R]
            MS8 --> MS9[复制数据到 L 和 R]
            MS9 --> MS10[双指针合并：i=0, j=0, k=left]
            MS10 --> MS11{L_i <= R_j?}
            MS11 -->|是| MS12[arr_k = L_i, i++]
            MS11 -->|否| MS13[arr_k = R_j, j++]
            MS12 --> MS14[k++]
            MS13 --> MS14
            MS14 --> MS15{还有剩余元素?}
            MS15 -->|是| MS11
            MS15 -->|否| MS16[复制剩余元素]
            MS16 --> MS17[合并完成]
        end

        %% 快速排序详细步骤
        subgraph 快速排序步骤
            QS1[开始：quickSort arr, low, high] --> QS2{low < high?}
            QS2 -->|否| QS3[返回]
            QS2 -->|是| QS4[pi = partition arr, low, high]
            QS4 --> QS5[递归：quickSort arr, low, pi-1]
            QS5 --> QS6[递归：quickSort arr, pi+1, high]
            QS6 --> QS7[分区过程：pivot = arr_high]
            QS7 --> QS8[i = low-1，双指针扫描]
            QS8 --> QS9[j 从 low 到 high-1]
            QS9 --> QS10{arr_j <= pivot?}
            QS10 -->|是| QS11[i++, swap arr_i, arr_j]
            QS10 -->|否| QS12[j++]
            QS11 --> QS12
            QS12 --> QS13{j < high?}
            QS13 -->|是| QS10
            QS13 -->|否| QS14[swap arr_i+1, arr_high]
            QS14 --> QS15[return i+1]
        end

        %% 随机化快速排序步骤## 标题 ##
        subgraph 随机化快排步骤
            RQS1[开始：randomizedQuickSort] --> RQS2{low < high?}
            RQS2 -->|否| RQS3[返回]
            RQS2 -->|是| RQS4[随机选择 pivot 索引]
            RQS4 --> RQS5[random_index = random low, high]
            RQS5 --> RQS6[swap arr_random_index, arr_high]
            RQS6 --> RQS7[调用标准 partition 过程]
            RQS7 --> RQS8[pi = partition arr, low, high]
            RQS8 --> RQS9[递归左半部分]
            RQS9 --> RQS10[递归右半部分]
            RQS10 --> RQS11[期望时间复杂度：O n log n]
        end

        E1 -.-> 插入排序步骤
        E2 -.-> 归并排序步骤
        E3 -.-> 快速排序步骤
        E4 -.-> 随机化快排步骤
    end

    %% 主方法节点
    subgraph 复杂度工具箱
        B --> MM["Master Method<br/>主方法<br/>T_n=a·T_n/b+f_n"]
    end
    MM -.->|Case 2: Θ n log n| E2
    MM -.->|Case 1: Θ n log n 平均| E3
    MM -.->|Case 1: Θ n log n 期望| E4

    subgraph 高级数据结构
        D4 --> F1[B-树]
        D4 --> F2[区间树/线段树]
        D4 --> F3[并查集 Disjoint-set]
        F3 --> F4[图最小生成树 Kruskal]
    end

    subgraph 图论
        D1 --> G1[图的表示：邻接表/矩阵]
        G1 --> G2[BFS & DFS]
        G2 --> G3[拓扑排序]
        G2 --> G4[强连通分量 SCC]
        G2 --> G5[最短路径：Dijkstra]
        G2 --> G6[最短路径：Bellman-Ford]
        G2 --> G7[最小生成树 Prim]
        G5 --> G8[所有点对最短路径：Floyd-Warshall]
        G6 --> G9[差分约束系统]
    end

    subgraph 动态规划
        E2 -.->|分治思想| H1[一维 DP：钢条切割/背包]
        H1 --> H2[二维 DP：LCS/编辑距离]
        H2 --> H3[区间 DP：矩阵链乘法]
        H3 --> H4[树形 DP：最优二叉搜索树]
    end

    subgraph 贪心
        E3 --> I1[活动选择问题]
        I1 --> I2[霍夫曼编码]
        I2 --> I3[最小生成树 Prim/Kruskal 贪心视角]
    end

    subgraph 摊还分析
        D4 --> J1[栈操作 & 二进制计数器]
        J1 --> J2[动态表扩张/收缩]
        J2 --> J3[斐波那契堆]
    end

    subgraph 高级算法
        G5 --> K1[A* 搜索]
        G2 --> K2[网络流：Ford-Fulkerson]
        K2 --> K3[最大流：Edmonds-Karp]
        K3 --> K4[最小费用最大流]
        H4 --> K5[字符串匹配：KMP]
        K5 --> K6[后缀数组/后缀树]
    end

    subgraph 复杂度理论
        B --> L1[P vs NP]
        L1 --> L2[NP-完全性：SAT, 3-CNF]
        L2 --> L3[近似算法：顶点覆盖, TSP]
        L2 --> L4[随机化算法：Miller-Rabin 素性测试]
        C --> L4
    end

    %% 样式定义
    style A fill:#ffe6cc
    style B fill:#ffe6cc
    style C fill:#ffe6cc
    style L1 fill:#f9f
    style L2 fill:#f9f
    style L3 fill:#f9f
    style L4 fill:#f9f
    style MM fill:#e6f7ff,stroke:#007acc
    
    %% 排序算法步骤样式
    style 插入排序步骤 fill:#f0f8f0,stroke:#28a745
    style 归并排序步骤 fill:#f0f4ff,stroke:#007bff
    style 快速排序步骤 fill:#fff5f0,stroke:#fd7e14
    style 随机化快排步骤 fill:#f8f0ff,stroke:#6f42c1
    
    %% 关键节点样式
    style IS10 fill:#d4edda,stroke:#155724
    style MS17 fill:#d1ecf1,stroke:#0c5460
    style QS15 fill:#f8d7da,stroke:#721c24
    style RQS11 fill:#e2e3f1,stroke:#383d41

快速排序厉害的地方在于一趟扫描让两批数据位于正确的地方，而不只是一个数据位于正确的地方。

数据结构

hashmap

LinkedHashMap

java 的实现是所有的节点都是双向链表的一部分，而每次 put 操作都往这个链表里加入一个节点。

增强版 hashMap-能够在 O(1) 时间里返回 key 的哈希表

class RandomizedSet {
    // 存储元素的值
    List<Integer> nums;
    // 记录每个元素对应在 nums 中的索引
    Map<Integer, Integer> valToIndex;
    
    public RandomizedSet() {
        nums = new ArrayList<>();
        valToIndex = new HashMap<>();
    }
    
    public boolean insert(int val) {
        // 若 val 已存在，不用再插入
        if (valToIndex.containsKey(val)) {
            return false;
        }
        // 若 val 不存在，插入到 nums 尾部，
        // 并记录 val 对应的索引值
        valToIndex.put(val, nums.size());
        nums.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        // 若 val 不存在，不用再删除
        if (!valToIndex.containsKey(val)) {
            return false;
        }
        // 先拿到 val 的索引
        int index = valToIndex.get(val);
        // 将最后一个元素对应的索引修改为 index
        int lastElement = nums.get(nums.size() - 1);
        valToIndex.put(lastElement, index);
        // 交换 val 和最后一个元素
        nums.set(index, lastElement);
        // 在数组中删除元素 val
        nums.remove(nums.size() - 1);
        // 删除元素 val 对应的索引
        valToIndex.remove(val);
        return true;
    }
    
    public int getRandom() {
        // 随机获取 nums 中的一个元素
        return nums.get((int)(Math.random() * nums.size()));
    }
}

比较巧妙的是，用list的index作为map的value，而map的key是原始 map 的value。这样就可以用一个满数组来保存所有的 key，而避开hashmap的槽空洞问题。

而 list 的 size 是一个隐藏的 current val 的 index。这个 index 不是 mod 出来的，而是增减出来的。

算法在计算中的作用

算法的定义

算法是良定义的计算过程，该过程输入某个值或者集合，产生某组值或集合。

• 解决问题：对于每个输入实例，算法能够停机。
• 效率：输入规模比较重要，常系数经常被记法（notation）隐藏，在同级算法比较中会有用。
• 硬件也是程序：后面我们会看到指令执行模型在算法中的体现。

数据结构的定义

存储和组织数据的方式。

算法基础

复杂度

编程语言特例

java

int[] nums = new int[n];

这个操作申请了一块n大小的区域，空间复杂度是 O(n)，时间复杂度也是 O(n)-因为对某些操作而言，初始化这批区域需要逐次初始化。

插入排序

循环不变式 loop invariant

• 初始化 initialization：循环第一次迭代以前，它为真
• 保持 mantainance：如果循环某次迭代前它为真，那么下次迭代之前它仍为真。
• 终止 termination：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。

我们使用循环不变式来证明了我们用插入排序解决了排序问题。这个方法和数学归纳法的区别是数学归纳法不一定终止，但循环不变式会终止。

分析算法

RAM 模型

在这个模型里，一切都是有限的（limited）：
- 指令只能在常量时间里执行
- arithmetic 加减乘除
- 赋值 load
- 控制
- 数据的字长有限（更广义地讲，内存有限）：我们不能引入无限存储
- 程序单线程执行
- 不考虑 memory hiarachy，否则问题会复杂得难以分析

基于这些假定，我们可以用一套伪代码来写所有算法，而且可以用统一的标准来衡量算法之间的复杂度。complexity（算法复杂度） is about step operation metric，我们在有限的资源里寻找合适消耗时间的算法。

插入排序的算法分析

• 运行时间是输入规模的函数
  • 我们研究的问题不同，输入规模的定义也不同：排序的输入规模是项数，而相乘的输入规模则是位数，图的输入规模是顶点和边的数量
  • 运行时间在我们写灯饰 T(n)=xxx 的时候，意味着我们在计算操作步数的总和

增长量级

我们通常只关心运行时间的增长率和增长量级，所以一个多项式里我们只关注最高阶项的阶数，它表示通用精度。常系数和低阶项我们都不关注，它们表示多余的精度。

设计算法

graph TD
    A[拿到最优解问题] --> B{决策点是什么?};
    B --> C{当前局部最优选择, 会影响全局结果吗?};
    C -- "不会 (无后效性)" --> D[✅ 贪心算法];
    C -- "会 (有后效性)" --> E{需要记录所有子问题解吗?};
    E -- "是, 状态复杂" --> F[✅ 动态规划];
    E -- "否, 只需几个变量记录历史极值" --> G[✅ 极值法/单次遍历];
    
    subgraph "其他思路"
        H{问题能拆成独立子问题吗?}
        H -- "能" --> I[✅ 分治法]
    end

    A --> H

flowchart TD
    A[分析问题] --> B{是否有时间/顺序约束？}
    B -->|有| C[考虑在线算法/流式处理]
    B -->|无| D[考虑批处理算法]
    
    C --> E{局部决策是否影响全局？}
    D --> F{子问题是否重叠？}
    
    E -->|不影响| G[贪心算法]
    E -->|影响| H[动态规划]
    
    F -->|重叠| I[动态规划]
    F -->|不重叠| J[分治算法]

分治法

1. 插入排序让我们引入了增量法，构造越来越大的子数组，待其等于主数组时，问题已被解决。
2. 分治法是让我们递归地重复以下过程：divide-conquer-merge。

当一个算法仅包含对其自身的调用的时候，我们可以使用递归方程来描述运行时间。

该方程根据在较小输入上的运行时间来描述在规模为 n 的问题上的总运行时间然后，我们可以使用数学工具来求解该递归式并给出算法性能的界。

使用递归树来计算 T(n) 的最坏情形：
递归树总是层为 lgn+1，高为 lgn，宽为c的树。假设叶子节点的代价为c。

则除根部以外每层的代价都相等，为 cn（c取归并、分解和单独操作的最大值就能归并c在不同层级之间不一致的问题），则除根部以外的总代价为 宽 * 高 * 每层代价 = cnlgn，加上根部 cn（D(n) + C(n)即分解和归并的代价。这种式子能写成c2，和解决子问题的c1取一个最大值c即可进入上界分析问题），总代价为 cnlgn + cn，所以这个算法的时间复杂度上界为 O(lgn)。

从鸽巢问题出发，我们看到什么

动态规划

动态规划的本质，是寻找状态的定义，并基于这个定义给出状态转移的方程。

最优子结构(optimal substructure）

定义

我们通常要做出一组选择来达到最优解。

在做每个选择的同事，通常会生成与原问题形式相同的子问题。当多于一个选择子集都生成相同的子问题的时候，动态规划通常就会很有效。其关键技术就是对每个这样的子问题都保存其解。档期重复出现时，可避免重复求解。

programming 其实是一种表格法，而非编程。分治法解决的问题是，互不相交的子问题。

最优解有两种： an optimal solution vs the optimal solution。

步骤

1. 刻画一个最优解的结构特征。
2. 递归地定义最优解的值。
3. 计算最优解的值，通过自底向上的方法。
4. 利用计算出的信息，构造一个最优解。

递归是自顶向下求解。
迭代可以自底向上求解。

能够用动态规划来解的问题通常具有两个性质：

• 最有子结构性质：问题的最优解，是由相关子问题的最优解组合而成，而这些子问题可以独立求解。
• 子问题重叠性质：最优子结构里可能出现的子问题，可能会产生重叠。

切割钢条问题

一般形式

要做基本的切割分析，得出切割方案的一般形式（因为对称性，我们总可以去掉一部分解），如：

rn = max(pn, r1 + r(n-1),…, rn-1 + r(1))

更进一步推导出具体形式：

rn = max(pn + rn-1)

递归调用树分析

借助递归调用树的节点总数，我们可以估计总调用次数。

需要通过证明，得知 T（n）= 2 的 n 次方（TODO）。

日后可以把它转化为子问题图：

动态规划的两种等价实现方法

动态规划仔细安排求解顺序，对每一个重复的子问题只求解一次，并将结果保存下来。

这是典型的时空权衡问题（time-memory trade-off）。

带备忘的自顶向下方法（top-down with memoization）。

贪心算法

与动态规划相似，贪心算法通常用于最优化问题。我们做出一组选择来达到最优解。贪心算法的四项，是每一步都追求局部最优解。

贪心选择性质的证明总是：假定一个存在一个最优解。最优解中的第一个选择如果可以被替换，替换成另一个贪心选择而能得到【另一个兼容】的最优解，则这个问题具有贪心选择性质。

只能用 dp 来解的问题，通常子问题的解是不能相容的，一个子问题的部分选择无法替换成另一个选择而让解的其他部分不变。贪心算法可以解决分数背包问题，不能解决0-1背包问题。因为0-1背包问题，把价值最高的解替换成功价值次高的解，有可能造成空间的变化，以至于让子问题的规模也得以变大-子问题的解可能也因此上升。

霍夫曼编码

霍夫曼具有贪心算法性质。
霍夫曼编码使用了一种前缀编码（prefix code），即没有任何码字是其他码字的前缀。使用这种前缀码，我们得到一串编码后可以唯一地解析出我们想要的信息，不产生二义性。

变长编码本身是一种变长编码（variable-length code），有点类似于 utf-8。核心思想是让拥有更高出现频率的 character 得到更短的码字。

摊还分析（amortized analysis）

摊还分析只能拿来分析一类特定的算法。摊还分析并不是通过分析每个操作的实际代价的界，来分析操作序列代价的界，而是直接分析序列整体的代价的界。这种方法的一个好处是，虽然某些操作的代价可能很高，但其他很多操作的代价可能很低。

Progamming Checklist

• 先写防御性编程方案。
• 然后写提前截断流程的子问题的答案。
• 开始用递归（自顶向下）或者迭代（自底向上）的方式求子问题的解，并逐渐推导到当前问题。

怎样把递归转迭代

必要条件

• 状态可保存：递归中的局部变量和参数能用栈保存

• 执行路径明确：能清晰地分离递归的各个阶段

• 迭代转递归：引入层次，然后用递归来进行探索，探索到了指定层次再执行。这会引入重复递归调用，因为每个递归只是为了到达某一层，而不可复用递归结果，所以所有O(n)会变成O(n^2)。

• 递归转迭代：引入一个 stack（LinkedList天然支持 push 和 pop，也支持 offer 和 poll）。然后把接下来要调用的所有参数按照逆序压入 stack 里。

二叉树的例子

二叉树的定义

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

前序遍历 - 迭代实现

import java.util.*;

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);  // 访问根节点
        
        // 先压入右子树，再压入左子树
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
    
    return result;
}

中序遍历 - 迭代实现

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    
    while (current != null || !stack.isEmpty()) {
        // 一直向左走到底
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        
        // 处理栈顶节点
        current = stack.pop();
        result.add(current.val);  // 访问根节点
        
        // 转向右子树
        current = current.right;
    }
    
    return result;
}

中序遍历 - 迭代实现

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    
    while (current != null || !stack.isEmpty()) {
        // 一直向左走到底
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        
        // 处理栈顶节点
        current = stack.pop();
        result.add(current.val);  // 访问根节点
        
        // 转向右子树
        current = current.right;
    }
    
    return result;
}

后序遍历 - 迭代实现

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Stack<TreeNode> stack = new Stack<>();
    TreeNode lastVisited = null;
    TreeNode current = root;
    
    while (current != null || !stack.isEmpty()) {
        if (current != null) {
            stack.push(current);
            current = current.left;
        } else {
            TreeNode peekNode = stack.peek();
            // 如果右子树存在且未被访问过
            if (peekNode.right != null && lastVisited != peekNode.right) {
                current = peekNode.right;
            } else {
                result.add(peekNode.val);
                lastVisited = stack.pop();
            }
        }
    }
    
    return result;
}

层序遍历（BFS）- 迭代实现

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> currentLevel = new ArrayList<>();
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            currentLevel.add(node.val);
            
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        
        result.add(currentLevel);
    }
    
    return result;
}

简单的通用递归转迭代模板

import java.util.*;

// 最简单的通用模板
public class SimpleRecursiveToIterative {
    
    // 简化版状态类
    static class SimpleState {
        int value;
        int step;  // 执行步骤
        
        SimpleState(int value, int step) {
            this.value = value;
            this.step = step;
        }
    }
    
    // 最简单的通用转换模式
    public static void simpleRecursiveToIterative() {
        // 1. 创建栈
        Stack<SimpleState> stack = new Stack<>();
        
        // 2. 初始化状态
        stack.push(new SimpleState(5, 0));
        
        // 3. 循环处理
        while (!stack.isEmpty()) {
            // 4. 弹出当前状态
            SimpleState current = stack.pop();
            
            // 5. 处理当前状态
            System.out.println("处理: " + current.value + ", 步骤: " + current.step);
            
            // 6. 推入下一个状态
            if (current.value > 0 && current.step < 2) {
                // 模拟递归调用
                stack.push(new SimpleState(current.value - 1, current.step + 1));
            }
        }
    }
    
    public static void main(String[] args) {
        simpleRecursiveToIterative();
    }
}

复杂递归转迭代示例

// 复杂递归示例
class State {
    TreeNode node;
    int phase;
    boolean flag;
    
    State(TreeNode node, int phase, boolean flag) {
        this.node = node;
        this.phase = phase;
        this.flag = flag;
    }
}

public void complexTraversal(TreeNode root) {
    if (root == null) return;
    
    Stack<State> stack = new Stack<>();
    stack.push(new State(root, 0, true));
    
    while (!stack.isEmpty()) {
        State state = stack.pop();
        TreeNode node = state.node;
        int phase = state.phase;
        boolean flag = state.flag;
        
        if (node == null) continue;
        
        if (flag) {
            if (phase == 0) {  // 阶段1
                doSomething1(node);
                stack.push(new State(node, 1, flag));  // 进入阶段2
                if (node.left != null) {
                    stack.push(new State(node.left, 0, false));
                }
            } else if (phase == 1) {  // 阶段2
                doSomething2(node);
                stack.push(new State(node, 2, flag));  // 进入阶段3
                if (node.right != null) {
                    stack.push(new State(node.right, 0, true));
                }
            } else if (phase == 2) {  // 阶段3
                doSomething3(node);
            }
        }
    }
}

private void doSomething1(TreeNode node) {
    System.out.println("Phase 1: " + node.val);
}

private void doSomething2(TreeNode node) {
    System.out.println("Phase 2: " + node.val);
}

private void doSomething3(TreeNode node) {
    System.out.println("Phase 3: " + node.val);
}

二叉树

graph TD
    A[二叉树 Binary Tree] --> B[完全二叉树 Complete Binary Tree]
    A --> C[满二叉树 Full Binary Tree]
    
    B --> D[完美二叉树 Perfect Binary Tree]
    C --> D
    B --> E[堆 Heap]
    
    D --> F[最大堆 Max Heap]
    D --> G[最小堆 Min Heap]
    E --> F
    E --> G

    A -->|特点| A1[每个节点最多两个子节点]
    B -->|特点| B1[除最后一层外都完全填满<br>最后一层从左到右填充<br>适合数组实现]
    C -->|特点| C1[每个节点要么0个子节点<br>要么2个子节点<br>无度为1的节点]
    D -->|特点| D1[所有层完全填满<br>所有叶子在同一层<br>节点数=2^h-1]
    E -->|特点| E1[父节点与子节点有序关系<br>支持优先队列操作]

    style A fill:#f9f,stroke:#333,stroke-width:3px
    style B fill:#e1f5fe,stroke:#333,stroke-width:2px
    style C fill:#fff3e0,stroke:#333,stroke-width:2px
    style D fill:#e8f5e8,stroke:#333,stroke-width:2px
    style E fill:#fce4ec,stroke:#333,stroke-width:2px

graph TD
    A[二叉树<br/>Binary Tree]
    B[完全二叉树<br/>Complete Binary Tree]
    C[满二叉树<br/>Full Binary Tree]
    D[完美二叉树<br/>Perfect Binary Tree]
    E[堆<br/>Heap]
    F[最大堆<br/>Max Heap]
    G[最小堆<br/>Min Heap]

    %% Features
    A1[每个节点最多两个孩子<br/>At most two children per node]
    B1[除最后一层外都满，最后一层从左到右填充<br/>Levels full except last, last filled left to right]
    C1[每个节点要么0个要么2个孩子<br/>Each node has zero or two children]
    D1[所有层都满，叶子同深度<br/>All levels full, leaves same depth]
    E1[父子保持顺序<br/>Parent-child order maintained]

    %% Applications
    B2[堆、优先队列、数组存储<br/>Heap, Priority Queue, Array storage]
    C2[表达式树、哈夫曼树、博弈树<br/>Expression Tree, Huffman Tree, Game Tree]
    D2[理论模型，高度约为 log2&#40;n&#43;1&#41;<br/>Theoretical model, Height ~ log2&#40;n&#43;1&#41;]
    E2[任务调度、Dijkstra、A*、操作系统优先队列<br/>Task scheduling, Dijkstra, A*, OS priority queue]
    F2[最大堆用于优先队列和堆排序<br/>Max Heap for PQ and Heap Sort]
    G2[最小堆用于调度和负载均衡<br/>Min Heap for Scheduling and Load balancing]

    %% Relationships
    A --> B
    A --> C
    B --> D
    C --> D
    B --> E
    D --> F
    D --> G
    E --> F
    E --> G

    %% Feature links
    A -->|特征 Feature| A1
    B -->|特征 Feature| B1
    C -->|特征 Feature| C1
    D -->|特征 Feature| D1
    E -->|特征 Feature| E1

    %% Application links
    B -->|应用 Application| B2
    C -->|应用 Application| C2
    D -->|应用 Application| D2
    E -->|应用 Application| E2
    F -->|应用 Application| F2
    G -->|应用 Application| G2

图算法

操作/属性	邻接矩阵	邻接表（链表）	邻接表（哈希表）
判断是否邻接	O(1)	O(n)	O(1)
添加边	O(1)	O(1)	O(1)
删除边	O(1)	O(n)	O(1)
添加顶点	O(n)	O(1)	O(1)
删除顶点	O(n2)	O(n + m)	O(n)
内存空间占用	O(n2)	O(n + m)	O(n + m)

回溯

/* 回溯算法框架 */
void backtrack(State state, List<Choice> choices, List<State> res) {
    // 判断是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
        // 不再继续搜索
        return;
    }
    // 遍历所有选择
    for (Choice choice : choices) {
        // 剪枝：判断选择是否合法
        if (isValid(state, choice)) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice);
            backtrack(state, choices, res);
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}

动态规划

动态规划状态分类表

类别	状态定义模式	典型问题	状态例子	特点
纯前缀型	只依赖「前i个元素」	- 最大子数组和（Kadane） - 最长公共子序列（LCS一维化前） - LIS（最长递增子序列）	dp[i] = 以第i个元素结尾的最优解	顺序天然递推，所有子结构都能用“以i结尾”覆盖
前缀 + 附加维度型	前缀索引 + 资源/条件维度	- 0/1背包、完全背包、多重背包 - 编辑距离（Levenshtein Distance） - 股票买卖问题（天数 + 持仓状态）	背包：dp[i][c] 编辑距离：dp[i][j] 股票：dp[day][hold]	不仅依赖前缀，还要记录额外约束（容量、操作数、状态机…）
区间型	子问题是区间 [l, r]	- 石子合并/矩阵链乘法 - 最长回文子序列 - 区间博弈	dp[l][r] = 区间[l…r]的最优解	子问题是区间划分，通常要枚举中点k来划分子区间
集合/图型（状压）	状态是「集合 + 当前位置」	- TSP（旅行商问题） - 最小斯坦纳树 - 子集覆盖问题	dp[mask][i] = 已访问集合为mask，当前在i的最优解	状态空间不是线性，而是子集或图节点；转移类似BFS/DFS