java - QuickHullアルゴリズムの複雑さ？

Question

私は複雑さがO（nlog（n））であることを知っています。しかし、なぜ？どうやってこの答えにたどり着きますか？

どんな助けでも大歓迎です、私は知ることに非常に興味があります！

Answer 1

その平均的なケースの複雑さはと見なされますがO(n log(n))、最悪の場合はO(n^2)（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パーティションは、右端の最低点と左端の最高点の2つの異なる極値を通る線によって決定されlます。極端なものを見つけるにはO(n)時間がかかります。

再帰関数のn場合、極値を決定するための手順が必要ですが、再帰呼び出しのコストは、setとsetzのサイズによって異なります。AB

最良の場合。各パーティションがほぼバランスが取れている場合の最良のケースを検討してください。次に、

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は2次式になります。

---

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