算法分析与设计-第11讲-期末复习与典型题解（2008秋）
北大算法分析与设计课程（屈婉玲）期末复习讲义：考试范围梳理 + 12 道典型题及题解。考试 2009-01-12。
考试范围三块
- 数学基础：估计函数的阶、递推方程求解、求和技术
- 算法设计技术：分治、动态规划、贪心、回溯与分支估界（理解给定例题并能简单应用）
- 算法分析技术：估计简单伪码的最坏/平均基本运算次数；清楚搜索、排序、选择三类问题的最优算法
知识点速记
函数阶
- f(n)=Θ(g(n)) ⇔ f(n)=O(g(n)) ∧ g(n)=O(f(n))；阶只反映 n>n0 的趋势，可忽略有限项，不允许抖动。
- 阶从高到低：指数级(2ⁿ,3ⁿ,n!) > 多项式级(n,n²,nlogn) > log 的多项式级。
- 排序题经典答案序：n! > n²ⁿ…（注：2^(n²) 级最高）> (3/2)ⁿ > (log n)^(log n)=Θ(n^log log n) > 2ⁿ > n³ > log(n!)=Θ(n log n) > n = 2^log n > log²n > log n > log log n > n^(1/log n)=Θ(1)。
递推方程
- 常系数线性齐次：无重根通解 Σci·qiⁿ；重根 qi(重数 ei) 对应 (c1+c2n+…+ciei n^(ei-1))qiⁿ；非齐次 = 齐次通解 + 特解。
- Master 定理（T(n)=aT(n/b)+f(n)）三情形：f=O(n^(log_b a − ε))→Θ(n^(log_b a))；f=Θ(n^(log_b a))→Θ(n^(log_b a)·log n)；f=Ω(n^(log_b a+ε)) 且 af(n/b)≤cf(n)(c<1)→Θ(f(n))。注意 n log n 不满足 case3（找不到 ε 使 n log n = Ω(n
- 递归树适合子问题不对称：选最长路径估层数、按层求和。
- 重要结果：f(n)=af(n/b)+d（常数 d）→ a≠1 时 O(n^log_b a)，a=1 时 O(log n)；d(n)=cn 时按 a<b / a=b / a>b 分别 O(n) / O(n log n) / O(n^log_b a)。
求和技术
- 等比级数有限和 a1(1−q^(k+1))/(1−q)；无穷收敛 a1/(1−q)（|q|<1）。
- 调和级数 Σ1/i = O(log n)；Σlog i = O(n log n)。
四大设计技术考点
- 分治：均衡划分、子问题类型同原问题、递归分析列递推方程。
- DP：优化问题+多步判断+最优化原则+子问题重叠；目标函数递推方程、自底向上、表格存储、解的追踪。
- 贪心：组合优化+贪心选择性质（要会证明）；局部优化策略确定。
- 回溯/分支估界：搜索问题+多米诺条件；约束条件（分支条件）与代价函数；效率可用 Monte Carlo 估计。
典型题解精要（12 题）
- 阶排序（见上）。
- 几何分布概率的顺序查找平均复杂度：p_i = p/2^(i−1) ⇒ p≈1/2，A(n)=2p(1/2+2/2²+…+n/2ⁿ)≈2，常数级平均复杂度。
- T1(n)=3T1(n/2)+n log n → Θ(n^log2 3)；T2(n)=T2(n−1)+1/n → Θ(log n)。
- T(n)=7T(n/2)+n=Θ(n^log2 7)，W(n)=aW(n/4)+n²：a>16 时 W=Θ(n^log4 a)，要 log4 a < log2 7 即 a<49，最大 a=48。
- 输出最大 i 个数（i<n^(1/2)）：算法A 反复 findmax = Θ(in)；排序法 Θ(n log n)；最优算法C：Select 选第 i 大 → 划分 → 只对 i 个元素排序，T=Θ(n)+Θ(i log i)=Θ(n)。
- 假币问题（不知轻重，天平）：三分法每次留 2n/3 嫌疑，T(n)≤T(2n/3)+O(1)=O(log n)；n<3 时用已确认合格币比对。
- 判定 x+y=s 是否存在：以 s/2 划分 A/B 两堆，对较小的堆排序，另一堆逐一二分检索，W(n)=O(n log n)。
- 集合中差最大/最小的两数：最大差=FindMaxMin 直接给出（⌈3n/2⌉−2 次比较）；最小差=排序后扫描相邻差，O(n log n)。
- 求 A∩B（|B|=m=O(log n)）：对小数集 B 排序后对 A 逐元素二分 → O(n log m)=O(n log log n)（枚举三种方案取优，是”选对排序对象”的示范题）。
- 输出全部区间和 B[i,j]：朴素三重循环 O(n³)；用 B[i,j]=B[i,j−1]+A[j] 递推降到 O(n²)；最优性证明用 2^i 幂次数列——B 的 O(n²) 个项两两不等，任何算法都要 Ω(n²)。
- 找离原点最近的 n 个点（题面应为 √n）：算全部距离 → Select 第 √n 小 → 线性过滤输出，T(n)=O(n)。
- 进程最少测试时刻：区间覆盖贪心（见作业）——按截止时间排序，在必须测试的最早时刻放测试点。