计算快速排序的平均案例复杂度

Question

我正在尝试使用递归关系为 Worst/Best/Average QuickSort 案例计算 big-O。我的理解是你的实现效率取决于分区函数的好坏。

最坏情况：枢轴总是留有一侧为空

• T(N) = N + T(N-1) + T(1)
• T(N) = N + T(N-1)
• T(N) ~ N²/2 => O(n^2)

最佳情况：主元平均划分元素

• T(N) = N + T(N/2) + T(N/2)
• T(N) = N + 2T(N/2) [大定理]
• T(N) ~ Nlog(N) => O(nlogn)

平均情况：这是我对如何表示递归关系或如何一般地处理它感到困惑的地方。

我知道快速排序的平均情况大O是O(nlogn)我只是不确定如何推导它。

Answer 1

当你选择主元时，最坏的情况是 0 | n，你能做的最好的就是 n/2 | n/2。一般情况下你会发现你得到的东西更像 n/4 | 3n/4，假设均匀随机。将其插入，一旦消除常量，您将得到 O(nlogn)。