快速凸包最坏情况的解释

Question

快速凸包算法的最坏情况是什么？我们如何知道它是最坏情况？ 我对快速凸包算法感到困惑。实际上，我理解运行行列式以找到三角形的面积，如果面积为正，则该点在极端点的左侧。 并且递归执行此操作将具有O(n)的效率来构建凸壳。 然后我不明白，为什么有时会提到O(nlogn)和O(n^2)的效率？在哪些情况下会出现这种效率，如何计算？ 如果有人能通过一些特定的示例帮助我，那将是很大的帮助。

- robot

---

当你在互联网上搜索时，你找到了什么？你确实进行了搜索吗？ - Mitch Wheat

Answer 1

恐怕接受的答案不正确。

事实上，上述情况是O(n log n)情况。只需看递归树即可。在每个步骤中，您将点集分成两个近似相等大小的子集。因此，递归树的高度为O(log n)，导致总运行时间为O(n log n)。

更精确地说：快速凸包算法的递推关系式为 T(n) = T(a * n) + T(b * n) + c*n。最后一项 (c*n) 表示查找轴心元素。在上面构造的情况下，常数 a 和 b 为 a = b = 1/2。您可以使用主定理确定O(n log n)的界限。

最坏情况 O(n²) 是 a*n ≈ n-1 和 b*n ≈ 1。您可以通过使用以下规则（极坐标）将点放置在圆的边缘来构造它：P_i = (r, π / 2ⁱ)。对于这组点，轴心元素始终是最左边的点，因此集合被划分为包含 n-1 个点和一个空子集的子集。因此，在递归的每个步骤中，您只“消除”一个点（轴心元素）。递归树的高度因此为O(n)，导致总效率为O(n²)。

- John

Answer 2

这是一个动画演示John's answer，演示每一步只有一个点被排除在考虑范围之外。

- rob mayoff

Answer 3

QuickHull是一种快速算法，因为在其中一步中，您可以消除位于三角形内部的一堆点。QuickHull的步骤如下：

1. 选择最右边和最左边的点，并在它们之间画出一条线
2. 找到距离该线最远的点
3. 在这三个点之间绘制一个三角形
4. 消除三角形内部的点并返回第2步。

当您的点随机分布在平面上时，就会遇到这种情况，但有些情况下，点的分布很糟糕，您无法在任何给定的步骤中消除任何一个点。其中一种情况是当点位于圆的边界上时：

正如您所看到的，在此情况下，算法的第4步根本不会消除任何点。这就是为什么在最坏的情况下，QuickHull的时间复杂度为O(n^2)。

- alestanis

---

很抱歉，这个答案不正确。请查看我的答案以获取详细说明。 - John