凸包算法时间复杂度疑问：排序后为何为线性时间？

你提到的是Andrew单调链凸包算法（或是Graham扫描的核心逻辑），核心误解在于：添加新点时根本不需要检查所有现有凸包点，只需要处理凸包链的末尾几个点，这就是为什么排序后的构建阶段是线性时间。

关键逻辑：转向检查与点的唯一操作 #

当点按x坐标（x相同时按y坐标）排序后，我们维护的是一条单调凸链（分为上链和下链，你说的左到右插入对应其中一条链的构建）。每次加入新点时，只做以下操作：

• 从当前链的末尾开始，依次取最后三个点，计算它们的转向（用叉积判断：如果叉积≤0，说明这三个点构成右转或共线，中间的点不在凸包上）；
• 只要满足转向条件，就删除中间的点，重复这个过程直到最后三个点构成左转，再把新点加入链尾。

为什么总操作是O(N)？ #

每个点只会被加入链一次，最多被删除一次：

• 被删除的点不会再被后续步骤处理；
• 所有点的插入和删除操作加起来总共是O(N)次，没有嵌套遍历所有点的情况。

你之前觉得是O(N²)，是把这个过程和"判断点是否在凸包内"的操作搞混了——这里完全不需要判断点是否在多边形内部，只需要通过简单的叉积计算就能快速筛选凸包点。

举个直观例子 #

假设排序后的点是P₁,P₂,P₃,P₄,P₅：

1. 先把P₁、P₂加入链；
2. 加入P₃时，检查P₁-P₂-P₃的转向，如果是右转，直接删掉P₂，再把P₃加入；
3. 加入P₄时，检查P₁-P₃-P₄的转向，是左转就直接加入；
4. 加入P₅时，检查P₃-P₄-P₅的转向，是右转就删掉P₄，再检查P₁-P₃-P₅的转向，是左转就加入P₅。
   整个过程里，每个点最多被操作两次，总次数是线性的。

额外说明：总算法复杂度 #

整个凸包算法的时间复杂度是O(N log N)，因为排序阶段是O(N log N)，而排序后的构建阶段是O(N)，取最大值。书中说的"排序后的总时间复杂度为线性"，指的是排序之后的构建步骤，不是整个算法的总复杂度。

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