QuickHull算法的复杂性？

Question

我知道复杂性是O(nlog(n)).但为什么？你是如何得出这个答案的？

任何帮助将不胜感激,我很有兴趣知道!

Answer 1

它的平均情况复杂度被认为是O(n log(n))，而在最坏的情况下则需要O(n^2)（二次）。

考虑以下伪代码：

QuickHull (S, l, r)

     if S={ }    then return ()
else if S={l, r} then return (l, r)  // a single convex hull edge
else
    z = index of a point that is furthest (max distance) from xy.
    Let A be the set containing points strictly right of (x, z)
    Let B be the set containing points strictly right of (z, y)
    return {QuickHull (A, x, z) U (z) U QuickHull (B, z, y)}

分区由穿过两个不同的极点的线确定：最右边的最低点r和最左边的最高点l。寻找极端情况需要O(n)时间。

对于递归函数，它需要采取n步骤来确定极限点z，但是递归调用的成本取决于set A和set 的大小B。

最好的情况。考虑每个分区几乎平衡时的最佳可能情况。那我们有

T(n) = 2 T(n/2) + O(n)。

这是一个熟悉的递归关系，其解决方案是

T(n) = O(n log(n))。

这将发生在随机分布的点上。

最坏的情况下。当每个分区极其不平衡时，会发生最坏的情况。在这种情况下，递归关系为

T(n) = T(n-1) + O(n) 
     = T(n-1) + cn

反复扩展表明这是O(n^2)。因此，在最坏的情况下，QuickHull是平方的。

http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/ConvexHull/quickHull.htm