3.6 下界
(Lower Bound)

我们已经得到了一个复杂度为 \(O(n \log n)\) 的凸包算法，那么我们能否做得更好？可能把复杂度做到 \(O(n)\) 吗？本节将证明这实际上是不可能的， \(n \log n\) 是任何凸包算法复杂度的"下界"。换句话说，任何凸包算法的时间复杂度都属于 \(\Omega(n \log n)\) 的集合，即，凸包算法的复杂度下界的为 \(\Omega(n \log n)\)。

计算机科学领域的研究人员发现，为问题建立非平凡的下界极其困难。难点在于，下界必须适用于任何可设想的情况，而要在一个证明中涵盖所有算法几乎是不可能的。 尽管如此，一些关键问题还是可以做到这一点的，尤其是排序问题。\(\Omega(n \log n)\) 是排序 \(n\) 个元素的下界。一旦某个问题的下界被确定，就可以通过"问题归约"来证明其他问题的下界。

假设已知问题 A 存在某个特定的下界。我们可以认为问题 A 的"难度"取决于该下界所体现的难度。因此，如果 A 的下界为 \(\Omega(n^4)\)，那么它是一个相当难的问题。 现在假设问题 A 可以归约到问题 B，即，求解问题 B 的算法，只需少量处理工作，就可以用于求解问题 A。如果我们能够快速求解 B，我们也能快速求解 A。 这就能得出 B 的一个下界，因为如果我们能够更快地求解 B，就会突破 A 的下界，这是矛盾的。

这也是我们找到凸包算法下界的的方法。我们将证明，如果我们能找到一个更快的凸包算法，就可以比 \(O(n \log n)\) 更快地完成排序。这已经被证明是不可能的。

使用凸包进行排序的初始方法是由 Shamos (1978) 提出的，非常简单。假设我们有一个待排序的无序数字列表 \(x_1, x_2, \dots, x_n, x_i > 0, \forall\)。这就是问题 A。 再假设我们有一个算法 B，它可以在 \(T(n)\) 时间内构造一个由 \(n\) 个点的凸包，即3.1.1节中提到的输出 (4)。 现在我们的任务是使用 B 在 \(T(n) + O(n)\) 的时间内求解问题 A，新增的 \(O(n)\) 表示将 B 的解转换为问题 A 的解所需的时间。

如图 3.9 所示，构造一组二维点 \((x_i, x_i^2)\)，这些点落在一条抛物线上。运行算法 B 构造抛物线的凸包。显然，每个点都在凸包上。 我们可以在 \(O(n)\) 的时间内找到凸包上的最低点 a，它对应的点 \(x_i\) 最小。从 a 开始逆时针方向，凸包上各点的排列顺序就是它们的排序顺序。 因此，我们可以使用凸包算法进行排序。

需要注意的是，算法 B 能够按顺序给出凸包周围的顶点，这一点对于此归约至关重要。如何将排序问题归约到按任意顺序识别包络线点的问题(输出(1)或(2)\)尚不明确。 多年来，确定寻找极点是否更容易，一直是个开放性问题。但有几位研究人员最终证实，\(\Omega(n \log n)\) 也是该问题的下界。