如何形式化证明凸包（Convex hull）算法时间复杂度下界为O(n log n)

前置已知条件 #

• 基于比较的排序算法的时间复杂度下界为Ω(n log n)：该结论由决策树模型推导可得，n个元素的排序结果共有n!种可能，对应决策树的n!个叶子节点，二叉树的最小高度为log₂(n!) = Ω(n log n)，因此不存在时间复杂度低于该下界的基于比较的排序算法。

归约构造（排序问题 → 凸包问题） #

我们通过线性时间归约，将排序问题的输入转化为凸包问题的输入，且凸包问题的输出可以线性时间转化为排序问题的输出，以此绑定两个问题的复杂度下界。
具体构造步骤：

1. 给定任意待排序的n个实数序列 A = {x₁, x₂, ..., xₙ}
2. 在线性时间*O(n)*内构造二维点集 P = {(xᵢ, xᵢ²) | xᵢ ∈ A}，即将每个实数映射到抛物线y=x²上的对应点。

构造点集的凸包性质 #

抛物线y=x²是严格下凸曲线，因此点集P中的所有点都属于该点集的凸包边界，且凸包顶点按逆时针顺序遍历的序列，其x坐标严格对应原实数从小到大的排序结果。

完整推理流程 #

假设存在基于比较的凸包求解算法，其时间复杂度为f(n) = o(n log n)（即时间复杂度优于O(n log n)），则可以按如下方式实现优于*O(n log n)*的排序算法：

1. 用*O(n)*时间将待排序实数序列转化为抛物线上的点集
2. 调用上述凸包算法得到凸包顶点的逆时针有序序列，时间开销为f(n)
3. 用*O(n)*时间遍历有序凸包顶点，提取每个点的x坐标，即可得到原实数序列的排序结果
   如果原实数序列存在重复值，构造的点集会出现重合点，凸包计算时会自动去重，我们仅需要在提取x坐标后按原序列计数还原即可，额外开销仍为线性时间，不影响复杂度推导。
   整个排序过程的总时间复杂度为 O(n) + f(n) + O(n) = f(n) = o(n log n)，这和基于比较的排序算法Ω(n log n)*的下界矛盾。

结论 #

基于比较的凸包求解算法的时间复杂度下界为Ω(n log n)。

内容的提问来源于stack exchange，提问作者Projekat Pr