quickhull算法中的最佳案例

Question

我想问一下在最好的情况下使用quickhull。基本上我有了快速的想法，并知道为什么最坏的情况和平均情况分别是O（n^2）和O（nlogn）。

但是，当最左边的点集合和最右边的点集合具有相同数量的点时，quickhull中的最佳情况会发生吗？其结果是，T（n）= T（n/2）+ O（n）≥0。

难道是这样，复杂度是T（nlogn）吗？你能告诉我最好的情况是怎么发生的，它的效率如何？

Answer 1

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

T（n）= 2 T（n/2）+ O（n）。

这使我们

T（N）= O（N的log（n））。

这会随机分布点发生。