算法设计与分析
集中回顾核心概念、公式和适用条件。
先看学习路线
按箭头顺序学习。点击一个阶段进入第一节；完整知识框架列出了每一个主题。
01 / 说明保证类型
最坏取同规模最难输入；期望对说明的随机性平均；摊还对操作序列平均。解释界之前先明确输入规模与算术成本模型。
02 / 表示的取舍
数组索引 O(1)，中间移动 O(n)。已知位置的双向链编辑 O(1)，但定位索引 O(n)。搜索与修改成本都要计入。
03 / BST 与 AVL
BST 搜索更新 O(h)，区间报告 O(h+k)。AVL 维持孩子高度差至多一，确保 h=O(log n)。k 为输出规模。
04 / 堆优先级
小顶堆父值不大于孩子。最小值 O(1)，插入与删最小 O(log n)。堆数组并未全排序。
05 / 哈希表假设
合适均匀哈希下，链地址查找期望 O(1+α)，α=n/m。线性探测删除需墓碑或修复簇。布谷鸟插入可能触发昂贵重建。
06 / 图遍历
邻接表 BFS、DFS 为 O(n+m)。BFS 最小化边数。无向 DFS 树边 (u,v) 在 low[v]>disc[u] 时为桥，必须正确处理父边。
07 / 路线与树
Dijkstra 松弛 d[u]+w(u,v)，要求非负权。Prim 用 w(u,v) 接新顶点。MST 最小化网络总权，不是源到各顶点距离。
08 / 贪心证明凭据
可分背包用密度与等重量交换，区间分配达到重叠深度，Huffman 合并最小两频。各证明依赖特定可行选择结构。
09 / 递推
T(n)=T(n/2)+Θ(1) 得 Θ(log n)；2T(n/2)+Θ(n) 得 Θ(n log n)；3T(n/2)+Θ(n) 得 Θ(n^log₂3)。包括拆分与合并成本。
10 / 排序与选择
随机快排排序两侧，期望 O(n log n)；Quickselect 只跟一侧，期望 O(n)。倒霉枢轴序列下，两者都可 Θ(n²)。
11 / 随机结构
Fisher–Yates 在固定位置 i 前均匀选 j∈{0,…,i}。跳表晋升概率一半时，操作期望 O(log n)，存储期望 O(n)。
12 / 读取输入长度
q 以 k≈log₂q 位编码时，√q≈2^(k/2)。相对数值的多项式可能对位长为指数，这对密码学复杂度很重要。