08 下界、近似算法与性能比

本章对应考试中的：简答 Q9（TSP 最近邻算法性能比）、Q10（求下界的方法）、Q11（排序下界与达到它的算法）、Q12（第二小值的下界，对手论证）、Q13（性能比陷阱）、Q16（16 球称重，紧下界）、判断题 16～19（排序/最值下界）、判断题 43～45（FPTAS 与性能比陷阱）、填空题第 5 题（性能比定义）、作业 O5（矩形切割近似）。

---

核心考点

这一章围绕两个主题：

1. 下界（lower bound）：解决某个问题至少需要多少次操作。考"求下界的方法"和具体下界值（排序、找最值、找第二小）。
2. 近似算法与性能比：对很难的问题求近似解，并衡量"近似解最坏能比最优解差多少倍"。考性能比的定义和它的经典陷阱。

---

从零开始的前置知识

什么是问题的下界

注意区分两个词：

• 算法的复杂度：某个具体算法要跑多少步，是一个上界（这个问题"最多这么多步能解"）。
• 问题的下界：任何算法解这个问题都至少要的步数。它刻画问题本身的难度。

举例：基于比较的排序，问题下界是 $\mathrm{\Omega }(n\log n)$，意思是"无论你用什么基于比较的排序算法，最坏情况都逃不掉 $n\log n$ 量级的比较次数"。

紧下界（tight lower bound）：如果存在一个算法的复杂度恰好等于这个下界，就说这个下界是"紧的"。否则只是一个"合法但不紧"的下界（比真实难度低估了）。

求下界的四种方法（Q10 考点）

1. 平凡下界（trivial lower bound）：按"必须读入的输入规模"或"必须输出的规模"得出。例：任何算法至少要把 $n$ 个输入看一遍，所以下界 $\mathrm{\Omega }(n)$。
2. 信息论下界 / 判定树下界（decision-tree lower bound）：把算法看成一棵"每次比较分两支"的判定树，要区分的结果有多少种，树就至少要多高。例：比较排序下界 $\mathrm{\Omega }(n\log n)$。
3. 对手论证（adversary argument）：假想一个"对手"，在不自相矛盾的前提下，对算法的每次询问都给出最刁难的回答，逼算法多做比较，从而证明下界。
4. 问题归约（reduction）：把一个已知下界的问题，转化（归约）到当前问题上，从而把已知下界"搬"过来。

Q10 原题就是"举出三种寻找问题下界的方法或策略"，上面四种任举三种即可。

判定树下界：为什么比较排序是 $\mathrm{\Omega }(n\log n)$

判定树（decision tree）：把一个"只靠比较来做决策"的算法画成二叉树，每个内部结点是一次比较（结果"$\le$"走左、"$>$"走右），每个叶子对应一种最终输出。

对 $n$ 个元素排序，可能的排列顺序有 $n!$ 种，所以判定树至少要有 $n!$ 个叶子来区分它们。一棵高度为 $h$ 的二叉树最多有 $2^h$ 个叶子，于是

$$2^h\ge n!⟹h\ge {\log }_2(n!).$$

而由斯特林公式 ${\log }_2(n!)=\mathrm{\Theta }(n\log n)$。树的高度就是最坏比较次数，所以比较排序的下界是 $\mathrm{\Omega }(n\log n)$。

判断题 16："基于比较的排序问题的下界是 $0.5n\log n$"——✓ 对，因为 $0.5n\log n=\mathrm{\Omega }(n\log n)$，是合法下界。

---

答题模板

求下界类：
  - 问"有哪些方法"→ 答：平凡下界、判定树/信息论下界、对手论证、问题归约（任举三种）。
  - 问"某问题的下界"→ 给出值 + 用上面某种方法简述理由 + 说明是否紧（有无算法达到）。

性能比类：
  - 定义：η = max{ c/c*, c*/c } ≥ 1（极小化取 c/c*，极大化取 c*/c）。
  - ⚠️ 单个实例的比值只是性能比的"下界"，不能断定算法性能比就是这个值——
    算法性能比是对"所有实例"取的最坏比值（上确界）。

---

逐题精解

Q11 排序下界与达到它的算法（2011期末/试卷4）

原题：给出基于比较的排序问题的最紧下界，并写出两个平均时间复杂度达到该下界的排序算法。

答案：最紧下界为 $\mathrm{\Omega }(n\log n)$（由判定树论证，见上）。平均时间复杂度达到 $O(n\log n)$ 的排序算法有：快速排序、随机化快速排序、合并（归并）排序、堆排序（任举两个即可）。

Q12 第二小值的下界（对手论证，2020，3 分）

原题：用对手论证法给出最坏情况下，从 $n$ 个数中找第二小值的基于比较算法的下界；这个下界是紧密的吗？

下界：$n+\lceil {\log }_{2}n\rceil -2$ 次比较。

论证：

• 要找第二小，必先确定最小值，这至少需要 $n-1$ 次比较（每个非最小元素至少要"输"一次才能被排除）。
• 第二小值一定在"曾经直接输给过最小值"的那些元素之中（它只可能败给最小值，不可能败给别人）。
• 采用锦标赛（tournament） 方法：把元素两两比较、胜者（较小者）晋级，像淘汰赛一样。最小值要一路赢到底，赢的场次等于淘汰赛的层数 $\lceil {\log }_{2}n\rceil$，也就是说最多有 $\lceil {\log }_{2}n\rceil$ 个元素直接和最小值比较过。
• 在这 $\lceil {\log }_{2}n\rceil$ 个"曾负于最小值"的元素里再找最小者，需 $\lceil {\log }_{2}n\rceil -1$ 次比较。
• 合计 $(n-1)+(\lceil {\log }_{2}n\rceil -1)=n+\lceil {\log }_{2}n\rceil -2$。

是否紧密：是紧密的——锦标赛方法恰好能用 $n+\lceil {\log }_{2}n\rceil -2$ 次比较达到这个下界，存在与下界一致的算法。

Q16 16 球称重（找最大与最小，试卷4）

原题：16 个外形一样但重量各不相同的小球，用一架没有砝码的天平，最少称几次能同时找出最重和最轻的球？为什么？

答案：22 次。 同时找最大值与最小值的比较次数紧下界是 $\lceil 3n/2\rceil -2$，$n=16$ 时为 ${\displaystyle \frac{3\times 16}{2}}-2=22$。

方法：

1. 把 16 个球两两配对比较（8 次），分成"较重的一组（8 个胜者）"和"较轻的一组（8 个败者）"；
2. 在"较重组"里用锦标赛找最重（8 个里找最大需 7 次）；
3. 在"较轻组"里找最轻（8 个里找最小需 7 次）；
4. 合计 $8+7+7=22$ 次。

判断题 17："找最大与最小值问题的下界是 $n/2$"——✓ 对（$n/2$ 是合法但不紧的下界，紧下界是 $\lceil 3n/2\rceil -2$）。

Q9 TSP 最近邻算法的性能比（样题1/试卷3）

原题：求解 TSP（旅行商问题）的最近邻居算法的性能比是多少？这一性能比是如何求得的？

前置：TSP（旅行商问题） 要找一条访问所有城市各一次再回到起点、总路程最短的回路。最近邻居（nearest-neighbor）算法 是贪心法：每次从当前城市走到最近的、还没去过的城市。

答案：最近邻居算法没有常数性能比——对一般（满足三角不等式的）TSP，它的性能比约为 ${\displaystyle \frac{1}{2}}(\lceil {\log }_{2}n\rceil +1)$ 量级，会随城市数 $n$ 增大而无界增长（不存在一个固定常数能卡住它）。

怎么求得的：构造一类特殊实例，使得贪心的"每次走最近"在后期被迫去走若干很长的边（因为近的城市都被先走光了），从而算出近似解与最优解之比的一个下界，并证明这个比值随 $n$ 增大而趋于无穷。（若课件给出具体结论，以课件为准。）

Q13 性能比陷阱（2020，2 分）

原题：若近似算法 A 求解某极小化问题一实例的解为 $s_a$，已知该问题最优解为 $s_a/3$，则该近似算法性能比是多少？为什么？

答案：仅凭这一个实例不能断定性能比为 3。这个实例只给出比值 ${\displaystyle \frac{s_a}{s_a/3}}=3$，它只是性能比的一个下界。算法的性能比定义为对所有实例取的最坏比值（上确界），必须对所有输入分析才能确定，可能大于 3。（与判断题 44/45 互相印证。）

---

性能比与近似算法（填空题 5、判断题 43～45）

性能比的定义（填空题第 5 题）

原题：最优值为 $c^{\ast }$，近似算法所得近似解对应的目标函数值为 $c$，则性能比定义为 $\eta =$（　）。

答案：

$$\eta =max\{\frac{c}{c^{\ast }},\frac{c^{\ast }}{c}\}.$$

含义：对极小化问题取 ${\displaystyle \frac{c}{c^{\ast }}}$（近似解更大、比值 $\ge 1$），对极大化问题取 ${\displaystyle \frac{c^{\ast }}{c}}$（最优更大、比值 $\ge 1$）。所以性能比恒 $\ge 1$，越接近 1 说明近似算法越好。

代入例子：极小化问题，最优 $c^{\ast }=10$，近似解 $c=13$，则该实例上 $\eta =13/10=1.3$。

FPTAS 的定义（判断题 43）

判断题 43："完全多项式近似方案是一个近似方案 $\{A_{\epsilon }\}$，其中每个 $A_{\epsilon }$ 在输入实例规模的多项式时间内运行"——✗ 错。

为什么错：完全多项式时间近似方案（FPTAS） 要求每个 $A_{\epsilon }$ 的运行时间关于输入规模 $n$ 与 ${\displaystyle \frac{1}{\epsilon }}$ 都是多项式。题目里只说了关于输入规模是多项式，漏掉了 ${\displaystyle \frac{1}{\epsilon }}$，所以错。（$\epsilon$ 是允许的相对误差，$A_{\epsilon }$ 保证性能比 $\le 1+\epsilon$。）

性能比的经典陷阱（判断题 44、45）

判断题 44："极小化问题某实例近似解 $s_a$、最优解 $s_a/3$，则性能比为 3"——✗ 错。 判断题 45："极大化问题某实例近似解 $s_a$、最优解 $2s_a$，则性能比为 2"——✗ 错。

为什么都错：单个实例的比值不等于算法的性能比。一个实例只给出性能比的一个下界；算法性能比必须取所有实例的最坏比值。这是历年最毒的判断陷阱之一，务必记牢。

---

判断题 18、19（找最值下界）

• 判断题 18："找最大值问题的下界是 $\mathrm{\Omega }(n/3)$"——✗ 错。找最大值需要 $n-1$ 次比较，紧下界是 $\mathrm{\Omega }(n)$；把"问题的（紧）下界"说成 $\mathrm{\Omega }(n/3)$ 是错的。
• 判断题 19："找最小值问题的下界是 $\mathrm{\Omega }(n/2)$"——✓ 对。找最小需 $n-1$ 次比较，$\mathrm{\Omega }(n/2)$ 是一个合法下界（虽不紧）。

注意 18 与 19 措辞几乎一样、答案却不同：差别在于"作为问题下界的判断"——$\mathrm{\Omega }(n/2)$ 被当作合法下界判对，而 $\mathrm{\Omega }(n/3)$ 这一条按题库答案判错。考试以题库给定答案为准，理解为"$n-1$ 才是真实需要、紧下界是 $\mathrm{\Omega }(n)$"。

---

作业 O5：矩形切割（条带装箱，试卷6，20 分）

原题：从一大张矩形材料（宽 $W$）中切割出一套矩形构件，使所用材料的高度 $H$ 最小。给出算法并分析运行时间。

要点：该问题（条带装箱 Strip Packing）是 NP 难 的（NP 难的含义见 09_P-NP理论与NP完全性证明.md），没有已知的多项式时间最优算法。常用近似算法，例如 NFDH / FFDH（按高度降序排列构件后，用 Next-Fit / First-Fit 策略一层一层地装）。作答时给出近似算法、分析其近似比与运行时间即可（按课件结论）。

---

高频陷阱 / 易错点小结

1. 单实例比值 ≠ 算法性能比（判断 44/45、Q13）：单实例只是下界，性能比要取所有实例最坏。
2. 性能比公式 $\eta =max\{c/c^{\ast },c^{\ast }/c\}\ge 1$，别漏 $max$、别记反极大/极小。
3. FPTAS 要对 $n$ 和 $1/\epsilon$ 都多项式（判断 43），漏掉 $1/\epsilon$ 就错。
4. 排序下界 $\mathrm{\Omega }(n\log n)$ 来自判定树 $2^h\ge n!$；$0.5n\log n$ 也算合法下界（判断 16 对）。
5. 第二小值下界 $n+\lceil {\log }_{2}n\rceil -2$、找最大最小紧下界 $\lceil 3n/2\rceil -2$，记住这两个公式（Q12、Q16）。
6. TSP 最近邻没有常数性能比（Q9），会随 $n$ 无界。

---

自测清单

• [ ] 说出求下界的三种方法（平凡 / 判定树 / 对手论证 / 归约 任三）。
• [ ] 解释为什么比较排序下界是 $\mathrm{\Omega }(n\log n)$（$2^h\ge n!$）。
• [ ] 写出第二小值下界 $n+\lceil {\log }_{2}n\rceil -2$ 并简述对手论证。
• [ ] 算出 16 球找最大最小需 22 次（$\lceil 3n/2\rceil -2$）。
• [ ] 默写性能比定义 $\eta =max\{c/c^{\ast },c^{\ast }/c\}$。
• [ ] 说清判断 43、44、45 为什么都错。