QuickHull算法的复杂性？ [英] Complexity of the QuickHull Algorithm?

问题描述

我知道复杂度是O（nlog（n））。但为什么？您如何得出这个答案？

任何帮助将不胜感激，我非常想知道！

解决方案

一般情况下，其复杂度为 O（n log（n）），而在最坏的情况下， O（n ^ 2）（二次）。

请考虑以下伪代码：

  QuickHull（S，l，r）
 
如果S = {}，则返回（）
否则S = {l，r}然后返回（l，r）//单个凸包边
否则
z =距xy最远（最大距离）的点的索引。 
设A为包含严格等于（x，z）的点的集合
设B为包含严格等于（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）。 / p>

这是一个熟悉的重复关系，其解决方案是

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

I know the complexity is O(nlog(n)). But why? How do you come to this answer?

Any help would be much appreciated, I'm very interested to know!

解决方案

Its average case complexity is considered to be O(n log(n)), whereas in the worst case it takes O(n^2) (quadratic).

Consider the following pseudo-code:

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)}

The partition is determined by the line passing through two distinct extreme points: the rightmost lowest r and the leftmost highest points l. Finding the extremes require O(n) time.

For the recursive function, it takes n steps to determine the extreme point z, but the cost of recursive calls depends on the sizes of set A and set B.

Best case. Consider the best possible case, when each partition is almost balanced. Then we have

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

This is a familiar recurrence relation, whose solution is

T(n) = O(n log(n)).

This would occur with randomly distributed points.

Worst case. The worst case occurs when each partition is an extremely unbalanced. In that case the recurrence relation is

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

Repeated expansion shows this is O(n^2). Therefore, in the worst case the QuickHull is quadratic.

---

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

这篇关于QuickHull算法的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！