2. 归约¶
2.1. 归约¶
本模块介绍一个理解问题之间关系的重要概念，称为 归约。 归约允许我们用一个问题来求解另一个问题。 同样重要的是，当我们想理解一个问题的难度时，归约使我们能够对问题的代价（而非算法或程序的代价）给出上限和下限的相对表述。
由于本章会大量讨论问题这一概念，我们希望有一种记法来简化问题描述。 在本章中，一个问题将由输入与输出之间的映射来定义，问题的名称全部用大写字母给出。 因此，排序问题的完整定义可以写成如下形式：
2.1.1. 归约与下界求解¶
Figure 10.2.1: 归约的一般过程，用"黑箱（blackbox）"图的形式表示。¶
2.2. 归约示例¶
2.3. 界定理¶
我们将使用如下记法： \(\leq_{O(g(n))}\) 表示可以用代价为 \(O(g(n))\) 的变换来完成一次归约。
下界定理（Lower Bound Theorem）： 如果 \(P_1 \leq_{O(g(n))} P_2\)， 且 \(P_1\) 的时间复杂度有下界 \(\Omega(h(n))\)，并且 \(g(n) = o(h(n))\)， 那么 \(P_2\) 的时间复杂度也有下界 \(\Omega(h(n))\)。 （注意是小 o，不是大 O。）
例子： SORTING \(\leq_{O(n)}\) PAIRING，因为 \(g(n) = n\)，\(h(n) = n \log n\)，且 \(g(n) = o(h(n))\)。 下界定理给出 PAIRING 的一个 \(\Omega(n \log n)\) 下界。
反过来也一样。
上界定理（Upper Bound Theorem）： 如果 \(P_2\) 的时间复杂度为 \(O(h(n))\)，且 \(P_1 \leq_{O(g(n))} P_2\)，那么 \(P_1\) 的时间复杂度为 \(O(g(n) + h(n))\)。
所以，给定良好的变换，两个问题的代价至少为 \(\Omega(P_1)\)，至多为 \(O(P_2)\)。 .. odsascript:: DataStructures/PIFrames.js .. odsascript:: AV/PIFLA/LimComp/Pair2SortFS.js .. odsascript:: AV/PIFLA/LimComp/LowerBoundFS.js .. odsascript:: AV/PIFLA/LimComp/TwoMulExampleFS.js
