通过替换法分析快速排序的最坏情况性能

Question

我正在尝试通过替换法解决快速排序算法的重现问题：

我找不到任何方法来证明这会导致 。我还需要采取哪些进一步的步骤才能完成这项工作？

Answer 1

我找到了我的问题的答案，上一个等式的延续是，

如果

，则为真

Answer 2

快速排序的最坏情况是当你从数组中选择一个作为最小或最大元素的枢轴元素时，使得所有剩余元素都转到分区的一侧，而分区的另一侧为空.在这种情况下，非空分区的大小为 (n - 1)，并且需要线性时间（kn 对于某个常数 k > 0）来进行分区本身，因此递推关系为

T(n) = T(n - 1) + T(0) + kn

如果我们猜测对于一些常数a、b、c，T(n) = an² + bn + c，那么我们可以代入：

an² + bn + c = [ a(n - 1)² + b(n - 1) + c ] + [ c ] + kn

其中方括号中的两个项分别是 T(n - 1) 和 T(0)。通过展开括号并使系数相等，我们得到

an² = an²

bn = -2an + bn + kn

c = a - b + 2c

由此得出一族解，由 c = T(0) 参数化，其中 a = k/2 和 b = k/2 + c。这一系列的解完全可以写成

T(n) = (k/2) n² + (k/2 + c) n + c

不仅是 O(n²)，而且是 Ө(n²)，这意味着 运行 时间是一个二次函数，不仅限于二次函数。请注意，c 的实际值不会改变函数的渐近行为，只要 k > 0（即分区步骤确实需要一定的时间）。