algorithm - 快速船体最坏情况说明

Question

快速船体最坏的情况是什么？以及我们如何知道这是我与快速船体算法混淆的最坏情况。实际上，我理解的是，求三角形面积的行列式，如果面积为正，则该点位于极值点的左侧。并且递归地做这件事，将有 O(n) 的效率来构建一个船体。那我就不明白了，有时提到如何提高效率是O(nlogn)和)(n^2)？在哪些情况下会产生这种效率以及如何产生这种效率？如果有人可以通过一些特定的例子提供帮助；那将是很大的帮助。

Answer 1

恐怕接受的答案不正确。

事实上，上面的情况就是O(n log n)的情况。只看递归树。在每个步骤中，您将点集切割成两个大致相等的子集。因此递归树的高度为O(log n)，导致总运行时间为O(n log n)。

更准确地说：quickhull 算法的递推关系是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 ² )。

Answer 2

这是John's answer的动画演示，展示了如何在每一步中只删除一个点：

Answer 3

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

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

当您的点随机放置在平面上时就是这种情况，但有些情况下点分布很差，您无法在任何给定步骤中消除它们中的任何一个。其中一种情况是当点在圆的边界内时：

如您所见，当发生这种情况时，在上述算法的第 4 步中，您根本没有消除任何点。这就是为什么在最坏的情况下 QuickHull 是O(n^2).