arrays - 保证分区后恒定差异时快速排序的最坏情况运行时

Question

我们想用标准的快速排序进行排序，我们保证，在调用分区方法之后，两个部分的大小差异最多是一个常数因子a。该算法的最坏情况运行时间是多少？

标签： arraysalgorithmsortingquicksort

Answer 1

由于分区之间的大小差异有限，快速排序是最坏情况 O(n log(n))

本质上，快速排序每次进行拆分时都会遍历整个数组。因此，我们只需要考虑最坏情况的分区，以及需要多少次拆分才能将其缩小到大小 1（或 2）。

现在，如果我们保证两个部分中较大的部分最多是另一个部分的 1 倍，那么最坏的情况是，较大的部分确实总是1倍大。

在这种情况下，快速排序中“层”的数量将等于我们必须将数组的原始大小除以 (1+a)/a 得到 1 的次数。这等于以 ( 1+a)/a 的输入大小。因为a是常数，所以 (1+a)/a 也是常数，因此分裂的数量是 O(log(n))，这意味着算法在 O(n log(n)) 最坏情况下运行。