Complexité de l’algorithme QuickHull?

Je sais que la complexité est O (nlog (n)). Mais pourquoi? Comment en venez-vous à cette réponse?

Toute aide serait très appréciée, je suis très intéressé de savoir!

Sa complexité de cas moyenne est considérée comme étant O(n log(n)) , alors que dans le pire des cas, elle prend O(n^2) (quadratique).

Considérons le pseudo-code suivant:

 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 ssortingctly right of (x, z) Let B be the set containing points ssortingctly right of (z, y) return {QuickHull (A, x, z) U (z) U QuickHull (B, z, y)} 

La partition est déterminée par la ligne passant par deux points extrêmes distincts: le plus bas à droite r et le plus à gauche l . Trouver les extrêmes nécessite O(n) temps.

Pour la fonction récursive, il faut n étapes pour déterminer le point extrême z , mais le coût des appels récursifs dépend des tailles des ensembles A et B

Meilleur cas. Considérons le meilleur cas possible, lorsque chaque partition est presque équilibrée. Ensuite nous avons

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

Ceci est une relation de récurrence familière, dont la solution est

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

Cela se produirait avec des points dissortingbués au hasard.

Pire cas. Le pire des cas se produit lorsque chaque partition est extrêmement déséquilibrée. Dans ce cas, la relation de récurrence est

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

Une expansion répétée montre qu’il s’agit de O(n^2) . Par conséquent, dans le pire des cas, le QuickHull est quadratique.


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