快速凸包算法的复杂度是什么？

Question

我知道这个复杂度是O(nlog(n))。但是为什么呢？你是怎么得出这个答案的？

非常感谢您的帮助，我非常想知道！

- I'LL BE BACK

---

这不是一个适合在http://math.stackexchange.com/或http://mathematica.stackexchange.com/上提问的好问题吗？ - Mike de Klerk

不，这是与编程有关的问题。 - I'LL BE BACK

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，但是递归调用的成本取决于集合A和集合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

- Xiao Jia

---

非常感谢您提供如此详细的答案！只有一个快速的问题……在伪代码中，它是否展示了分治技术？那是最后一行吗？ - I'LL BE BACK

@user1846486 是的，就是最后一行。这种风格与快速排序算法完全相同，因此被称为Quickhull :-) - Xiao Jia

好的，谢谢！最后，您知道如何解决递归方程吗？您只是把T(n)的值代入T(n)中吗？我在某个地方读到过，但是这样做肯定会使2T呈指数增长吧？ - I'LL BE BACK

通常我使用主定理，或者猜测和检查的方法。主定理可以解决大部分问题。 - Xiao Jia

非常感谢。如果您能成为我的老师，我会非常高兴！祝您有美好的一天。 - I'LL BE BACK