Сложность алгоритма QuickHull?

Его средняя сложность случая считается 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