Quick Hull Worst案例解释

Question

快速船体的最坏情况是什么？我们如何才能知道这是最糟糕的情况,我对快速船体算法感到困惑.实际上,我明白,运行行列式来找到三角形的区域,如果区域是正的,则该点位于极值点的左侧.并且递归地执行此操作,将具有构造船体的O(n)效率.然后我不明白,有时提到如何提高效率O(nlogn)和(n ^ 2)？在哪些情况下,这种效率结果如何？如果有人可以通过一些特定的例子帮助,请 那将是很大的帮助.

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)表示搜索pivot元素.在上面构造的情况下,常数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

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

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

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

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