第6章 答题与复杂度：让阅卷者看得懂、验得对
第6章 答题与复杂度：让阅卷者看得懂、验得对¶
本章把算法思路变成一份可评分的答案：变量语义清楚、核心过程不被函数名掩盖、边界可追踪、复杂度与代码一致。
b_181_5；PDF 第 181 页 · b_181_66.1 代码书写和可抽象的边界¶
注释应该写在哪里？¶
只写对判断正确性有帮助的注释： - 变量定义处：说明指针、计数器、辅助数组的语义。 - 关键更新处：说明为什么移动指针、改变入度或更新最优值。 - 非显然边界处：说明空表、首尾结点、访问标记和失败返回。
不要给 i++ 这类显然语句写逐字注释；注释应补足“为什么”，而不是重复“做了什么”。
b_181_7；PDF 第 181 页 · b_181_8；PDF 第 181 页 · b_181_9；PDF 第 181 页 · b_181_12辅助函数可以只写函数名吗？¶
判断标准不是固定行数，而是：该过程是否正在替你完成本题的主要考点。
- 考快排，就必须写划分和递归的核心过程。
- 考树遍历，就必须写出遍历顺序与 visit 位置。
- 若交换、取最小值、入队等只是辅助操作，可写简短调用，但要保证参数和语义清楚。
⚠️ 原讲义“超过 5 行或占全部代码 1/4”只是经验性阈值，不是评分细则。
b_182_3；PDF 第 182 页 · b_182_4；PDF 第 182 页 · b_182_5INT_MAX、INT_MIN 怎样用才不会把初值设反？¶
- 求最小值：初值设为足够大的值，如 INT_MAX。
- 求最大值：初值设为足够小的值，如 INT_MIN。
- 每读到一个候选值，就与当前最优值比较并更新。
⚠️ 校订：INT_MAX 和 INT_MIN 是 limits.h 中的宏，不是“C 语言自带函数”。如果后续还要对哨兵初值做加减，必须先防止整数溢出。
b_182_6；PDF 第 182 页 · b_182_7；PDF 第 182 页 · b_182_8min/max、输入输出和 swap 哪些细节最容易写错？¶
- min/max 可使更新式更紧凑，但不要重复求值带副作用的表达式。
- C 语言 scanf 中，标量通常传地址；字符数组作字符串输入时用数组名，不要照抄原讲义的 &d。
- C++ 的 swap(a,b) 可用引用参数；C 语言若要在函数内交换调用者变量，要传指针。
- 若输入输出不是考点，用“读入……/输出……”的规范伪代码，往往比写错格式串更稳。
b_182_11；PDF 第 183 页 · b_183_0；PDF 第 183 页 · b_183_4；PDF 第 183 页 · b_183_6a[i++] 和 a[++i] 分别先做什么？¶
- a[i++]：先用当前 i 访问数组，再使 i 增 1。
- a[++i]：先使 i 增 1，再用新的 i 访问数组。
例：i=0，a[0]=0，a[1]=1，则 x=a[i++] 得到 0；重置 i=0 后，x=a[++i] 得到 1。
⚠️ 不要在同一表达式中对 i 做多次无明确次序的读写；算法题宁可拆成两行，换取可读性与可验证性。
b_184_2；PDF 第 184 页 · b_184_3；PDF 第 184 页 · b_184_4；PDF 第 184 页 · b_184_7原讲义的冒泡排序示例可以直接背吗？¶
不能。原页的循环边界和比较下标并不是标准冒泡排序：它固定使用 A[i] 与 A[j] 比较，且外层条件 i>1 会漏掉最后一轮。
如果需要冒泡排序，应保证每轮比较的是相邻元素 A[j] 与 A[j+1]，把当前未排序区间的最大（或最小）元素逐步交换到边界；外层共需至多 n-1 轮，并可用“本轮是否发生交换”提前结束。
这张卡的目的不是新增一个排序考点，而是提醒：回源定位到原稿，不等于原稿代码必然正确；先验证循环不变式再背。
b_184_10；PDF 第 185 页 · b_185_0；PDF 第 185 页 · b_185_1；PDF 第 185 页 · b_185_46.2 复杂度不靠“看起来”¶
大 O 到底表示什么？¶
\(T(n)=O(f(n))\) 表示：存在常数 \(c>0,n_0\)，当 \(n\ge n_0\) 时，\(0\le T(n)\le c f(n)\)。它给出渐近上界，不是说 \(T(n)\) 与 \(f(n)\) 必须精确相等。
做题时通常给出尽可能紧的阶： - 多项式取最高阶，忽略常数因子和低阶项。 - 对数的底为大于 1 的常数时，换底只差常数因子，因此大 O 中可简写为 \(\log n\)。 - “默认最坏情况”是讲义的应试口径；如题干明确问平均、最好或期望，必须按题干。
⚠️ 快排不是“永远只算平均”：平均时间 \(O(n\log n)\)，最坏时间 \(O(n^2)\)；递归栈平均 \(O(\log n)\)，最坏 \(O(n)\)。
b_185_5；PDF 第 185 页 · b_185_6；PDF 第 185 页 · b_185_8；PDF 第 185 页 · b_185_10多层循环为什么有时相乘，有时要求和？¶
- 范围独立：外层 \(n\) 次，内层每次都 \(n\) 次，可直接相乘得 \(O(n^2)\)。
- 范围依赖外层变量：写成总次数之和，如 \(\sum_{i=0}^{n-1} i=\Theta(n^2)\)。
- 指数增长：先列外层值，再求各轮内层工作量。讲义中 i=1,2,4,…、内层做 i 次的例子，总和 \(1+2+\cdots+2^k=\Theta(n)\)，不是 \(O(n\log n)\)。
💡 统一问法：第 i 轮做多少次？把它从所有 i 上加起来。
b_186_2；PDF 第 186 页 · b_186_5；PDF 第 186 页 · b_186_8；PDF 第 186 页 · b_186_10递归的时间和空间为什么不是同一个数？¶
- 时间看总共产生多少个调用，以及每个调用做多少非递归工作。
- 辅助空间看同一时刻调用栈最深叠多少层，即最大递归深度。
二叉树遍历中，每个结点只做常数工作，时间是 \(O(n)\)；栈深为树高 \(h\)，空间是 \(O(h)\)，最坏退化成链时才是 \(O(n)\)。
b_186_11；PDF 第 186 页 · b_186_12；PDF 第 187 页 · b_187_5；PDF 第 187 页 · b_187_6空间复杂度到底数哪些空间？¶
算法分析通常数随问题规模增长的额外空间： - 若输入数组、原树由题目已给，不把它们本身的占用重复算作辅助空间。 - 新建长度为 \(n\) 的数组、\(n\) 个新结点或访问标记表，计 \(O(n)\)。 - 固定个数的标量、指针是 \(O(1)\)。 - 递归另计最大调用栈深度。
⚠️ 不要只看函数内有没有 malloc；一个循环创建 \(n\) 个结点就是 \(O(n)\) 额外空间。
b_187_0；PDF 第 187 页 · b_187_1；PDF 第 187 页 · b_187_3；PDF 第 187 页 · b_187_46.3 三问式答案怎样一次写顺¶
设计思想、代码和复杂度如何一一对应？¶
草稿纸上先做四步： 1. 把大问题拆成 2～5 个模块，画出输入、状态更新和输出。 2. 先估算各模块复杂度，确认达到题干目标。 3. 用完整句子把模块顺序写成第（1）问。 4. 把每个句子翻译成一段代码，最后按实际循环、递归和辅助结构写第（3）问。
终检清单：参数是否含长度；头结点口径是否一致；空/单元素是否退出；数组是否越界；返回值是数值还是下标；复杂度是否把排序、递归栈算进去。
b_188_1；PDF 第 188 页 · b_188_2；PDF 第 188 页 · b_188_3；PDF 第 188 页 · b_188_5；PDF 第 188 页 · b_188_6写不出来时，怎样判断是思路问题还是代码模块问题？¶
- 连流程图都画不出：先只练“输入 → 状态 → 更新 → 输出”，不急着写 C。
- 流程完整，某一块翻译不出代码：单独补这个模块，如折半边界、快排划分、链表删除、BFS 入队时机。
- 代码能写，但经常越界/死循环：不要继续背整段代码，改为说清循环不变式和终止条件。
复盘的产物应是一张“我缺哪个可迁移模块”的清单，而不是笼统的“我数据结构不行”。
b_188_8；PDF 第 188 页 · b_188_9；PDF 第 188 页 · b_188_10；PDF 第 188 页 · b_188_13；PDF 第 188 页 · b_188_142011 年双序列中位数题，怎样用两个层级作答？¶
保底层：用两指针归并两个有序数组，再取题目定义的中位位置。时间 \(O(n)\)；若完整存储结果则空间 \(O(n)\)，只归并到目标位置可把额外空间降为 \(O(1)\)。
最优层：利用两序列等长且有序，每轮比较两者中位数，成对舍弃不可能包含总中位数的两段，并保持剩余候选数量对称。时间 \(O(\log n)\)，空间 \(O(1)\)。
⚠️ 原讲义 p190 的合并代码有 OCR 错位，不应逐字背诵；题干对“中位数位置”的定义要按原题处理，不能自行改成常见统计学定义。
b_188_15；PDF 第 188 页 · b_188_16；PDF 第 189 页 · b_189_4；PDF 第 189 页 · b_189_8；PDF 第 190 页 · b_190_56.4 全书一张路线图¶
顺序表、链表、树和图的第一反应分别是什么？¶
| 对象 | 首先检查 | 常用主线 | 最常见失误 |
|---|---|---|---|
| 顺序表/数组 | 有序、值域、能否改顺序、空间限制 | 枚举 → 排序/折半/散列/预处理/多指针 | 无视下标语义，不必要地对全部排序 |
| 链表 | 带头结点否、单/双/循环、能否改链 | 前后指针、快慢指针、逆置、散列 | 丢失 next，头结点口径混乱 |
| 树 | 结点定义、需要哪种遍历顺序 | 写空树出口 → 左/右递归 → 填 visit/合并返回值 | 不相信递归语义，在每个结点重复扫整棵子树 |
| 图 | 有向/无向、带权否、存储方式、是否连通 | DFS/BFS；再按目标选最短路、MST、拓扑 | 忘访问标记，把不适用算法用于负权或非连通场景 |
💡 统一主线：先确认结构和约束，再选遍历/更新状态的模板，最后检查边界和复杂度。
b_191_0；PDF 第 192 页 · b_192_0；PDF 第 193 页 · b_193_0