algorithm - quickhull 算法中的最佳案例

Question

我想问一下最好情况下的quickhull。基本上我得到了 quickhull 的想法，并且知道为什么最坏情况和平均情况分别是 O(n^2) 和 O(nlogn)。

但是，当最左边的点集和最右边的点集具有相同数量的点时，quickhull 中的最佳情况会发生吗？

因此，T(n)=T(n/2)+O(n)？

是不是这样，复杂度是T(nlogn)？你能告诉我最好的情况是如何发生的及其效率吗？

Answer 1

最佳情况发生在每个分区几乎平衡时。所以我们有

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

这导致我们

T(n) = O(n log(n))。

这会发生在随机分布的点上。