快速排序的最佳案例性能（波浪符号）

Question

我的教授说快速排序的最佳情况是拆分平衡时（即当基准始终是中间的元素时）。

现在可以使用递归关系确定最佳情况快速排序的复杂度，如下所示：

T(n) = 2*T(n/2) + partitioning(n)

在下一步中他说：

因此= ~n * log2(n)

有人可以详细说明您是如何准确计算这个的。我到处搜索了很多，但所有的解释都是大哦符号，或者没有真正解释循环是如何 solved/calculated.

Answer 1

我将在这个答案中解决 Tilde Notation，假设 partitioning(n) 本身就是 ~n，这意味着它会及时运行 G(n) = n + C。

在这种情况下，最佳情况的复杂度函数是：

带有 T(1) = 1+C

的基本子句

T(n) = 2T(n/2) + (n+C)

声明：对于所有 n>0:

T(n) = n(1+logn) + (2n-1)C

归纳法证明。
基础条款：对于T(1)，声明作为基础成立。

T(n) = 2T(n/2) + (n + C)
T(n) = 2(n/2 log(n/2) + n/2 + (n-1)C) +(n + C) //induction hypothesis
T(n) = nlog(n/2) + n + (2n-2)C + n  + C
T(n) = nlog(n/2) + nlog(2) + n + (2n-2)C + C
T(n) = nlog(n/2 * 2) + n +(2n-2+1)C
T(n) = n(logn+1) + (2n-1)C

从T(n) = nlogn + (2C+1)n - C开始，我们可以断定确实是~nlogn。

Answer 2

答案来自Master Theorem.

快速排序的最佳运行时间的递归关系是：

T(n) = 2T(n/2) + Θ(n)

主定理将递推关系概括为以下形式：

T(n) = aT(n/b) + f(n)

比较两个方程：

a = 2

b = 2

f(n) = Θ(n)

因为 f(n) = Θ(n)，来自大师定理的情况 2：

If f(n) = &theta;(n<sup>log<sub>b</sub>a</sup>), then T(n) = &theta;(n<sup>log<sub>b</sub>a</sup>lg(n))

因此，Quicksort 在最佳情况下的时间复杂度降低到

T(n) = Θ(n lg(n))

编辑：如果您问为什么它是波浪符号 ~n * log2(n) 而不是 Big-O 符号，那是因为在您的情况下，目标必须是创建运行时间的近似模型（不忽略常量（如果有的话）而不是制定复杂性的上限。此外，波浪符号对于预测性能非常有用，而大 O 符号则不是。

快速排序的最佳案例性能（波浪符号）

Best case performance of quicksort (tilde notation)

sorting

algorithm

quicksort

time-complexity