1数学地基自查（三）
写下你的答案。
计算机基础 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2这批课在考研里的位置
把这两块的知识框架各画一张图。
3阶段小结
回头看地基期，哪门课改变了你看程序的方式？
4算法分析：从会写到会证
你写过的哪个算法，你只是"觉得"它对？
5渐进记号的严格定义
说"快排是 O(n²)"错吗？
6为什么忽略常数
什么时候常数不能忽略？
7最好最坏平均
哈希表查找的三种情况分别是多少？
8摊还分析
动态数组的插入摊还复杂度是多少？
9摊还的三种分析法
用聚合法算动态数组：插入 n 次总代价多少？
10递归式求解：代入法
猜 T(n)=2T(n/2)+n 是多少？
第 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贪心的正确性
什么是交换论证？
第 3 页 · 正面（题目）
21活动选择的证明
为什么换了还可行？
22贪心失效的例子
贪心和最优各是多少枚？
23拟阵
这告诉我们什么？
24动态规划的两个条件
最短路满足最优子结构吗？
25什么时候最优子结构不成立
这说明什么？
26状态设计是核心
背包问题为什么状态要带容量？
27从记忆化到递推
递推的顺序怎么定？
28滚动数组
一维背包为什么要倒序遍历容量？
29区间动规
矩阵链乘的复杂度是多少？
30树形动规
树上最大独立集怎么设状态？