1数学地基自查（三）
写下你的答案。
计算机基础 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2这批课在考研里的位置
把这两块的知识框架各画一张图。
3阶段小结
回头看地基期，哪门课改变了你看程序的方式？
4算法分析：从会写到会证
你写过的哪个算法，你只是"觉得"它对？
5渐进记号的严格定义
说"快排是 O(n²)"错吗？
6为什么忽略常数
什么时候常数不能忽略？
7最好最坏平均
哈希表查找的三种情况分别是多少？
8摊还分析
动态数组的插入摊还复杂度是多少？
9摊还的三种分析法
用聚合法算动态数组：插入 n 次总代价多少？
10递归式求解：代入法
猜 T(n)=2T(n/2)+n 是多少？
第 1 页 · 背面（答案）
参考答案（家长）：概率从事件到分布到推断；线代从向量到矩阵到特征值。
参考答案（家长）：用阈值比较、减少步数避免相近相减、精度提十倍点数要百倍。
参考答案（家长）：贪心类最常见，直觉对但没证明过。
参考答案（家长）：常见的答案是组成原理和操作系统，因为它们解释了"为什么"。
参考答案（家长）：n 不大时，常数小的朴素算法反而更快。
参考答案（家长）：不错，只是上界给松了，最坏确实是平方。
参考答案（家长）：常数，因为扩容的代价被之前的便宜插入分摊了。
参考答案（家长）：最好和平均是常数，最坏是线性。
参考答案（家长）：n 乘 log n。
参考答案（家长）：扩容总代价约 2n，平均每次常数。
第 2 页 · 正面（题目）
11递归树法
画出归并排序的递归树。
12主定理
T(n)=2T(n/2)+n 属于哪种情况？
13主定理的三种情况
T(n)=4T(n/2)+n 是哪种？
14主定理用不了的时候
T(n)=T(n/3)+T(2n/3)+n 怎么办？
15分治的三步
归并排序的合并为什么是线性的？
16分治求最近点对
窄带里为什么只需检查常数个点？
17分治求逆序对
为什么合并时能统计？
18快速选择
为什么只递归一侧就快了？
19线性时间选择
它实际常用吗？
20贪心的正确性
什么是交换论证？
第 2 页 · 背面（答案）
参考答案（家长）：两者同阶，结果是 n log n。
参考答案（家长）：log n 层、每层总代价 n，合计 n log n。
参考答案（家长）：画递归树，深度 log n，结果仍是 n log n。
参考答案（家长）：递归占优，结果是 n 的平方。
参考答案（家长）：距离下界保证了窄带内点不会太密集。
参考答案（家长）：两个有序序列用双指针一遍扫完。
参考答案（家长）：每次问题规模减半，总代价是等比数列而非 n log n。
参考答案（家长）：右边元素先出时，左边剩余的全都和它构成逆序对。
参考答案（家长）：假设有最优解与贪心不同，逐步换成贪心的选择而不变差。
参考答案（家长）：不常用，常数太大，实践中随机快速选择更快。
第 3 页 · 正面（题目）
21活动选择的证明
为什么换了还可行？
22贪心失效的例子
贪心和最优各是多少枚？
23拟阵
这告诉我们什么？
24动态规划的两个条件
最短路满足最优子结构吗？
25什么时候最优子结构不成立
这说明什么？
26状态设计是核心
背包问题为什么状态要带容量？
27从记忆化到递推
递推的顺序怎么定？
28滚动数组
一维背包为什么要倒序遍历容量？
29区间动规
矩阵链乘的复杂度是多少？
30树形动规
树上最大独立集怎么设状态？
第 3 页 · 背面（答案）
参考答案（家长）：贪心 4+1+1 三枚，最优 3+3 两枚。
参考答案（家长）：结束更早，后面的活动更不容易冲突。
参考答案（家长）：满足，最短路的任一段也是最短路。
参考答案（家长）：贪心能不能用，是有统一判据的，不靠猜。
参考答案（家长）：剩余容量决定了后面还能选什么。
参考答案（家长）：动规不是万能的，要先验证性质再用。
参考答案（家长）：保证用到的是上一层的值，避免同一物品被选多次。
参考答案（家长）：保证算某个状态时它依赖的状态都已算好。
参考答案（家长）：每个点两个状态：选它和不选它。
参考答案（家长）：n 的三次方。