algorithm - 在快速排序中，如果拆分为 5 : n-5, 那么时间复杂度将是？

Question

当分区大小之间的比率为 5:n-5 或类似 1:19 时，您如何找到快速排序的复杂性？我不太明白在这些情况下如何计算算法的复杂度。

Answer 1

一般来说，请记住以下几点:

• 如果您将一个数组分成两个部分，每个部分由 a:b 的某个固定比率定义，则在 O(log n) 次拆分后，子数组的大小将降至 0。

  <

• 如果将数组拆分为两个部分，其中一个大小为常量 k，则需要进行 Θ(n/k) 次拆分才能使子数组大小降至 0。

现在，想想快速排序在每个递归级别上所做的工作。在每一层，它需要做的工作与层中元素的数量成正比。如果您使用第一种方法并进行类似 1/20 : 19/20 的拆分，那么每层最多有 n 个元素，但只有 O(log n) 层，因此完成的总工作量将为 O(n log n)，太棒了。

另一方面，假设您总是使用五个元素。然后，每一步的较大数组的大小为 n、n - 5、n - 10、n - 15、...、10、5、0。如果你算出数学并将其求和，则得出 Θ (n²) 总工作量，效率不高。

一般来说，快速排序尽量避免一次拆分固定数量的元素。这给了您需要担心的退化情况。