我如何证明快速排序的主定理

Question

我有一个关于算法的问题，快速排序。 有人可以解释我如何得到结果（证明） 2T(n/2) + Θ(n) 吗？ 结果意味着什么：T(n-1) + Θ(n).

谢谢大家的回答。

Answer 1

主定理指出，

任意 ,

1. 如果 for some constant , then .
2. 如果, then .
3. 如果, for some constant , and if for some constant and all sufficiently large , then

至于你的，
,

这里，
（第二个条件）
所以复杂度将是：

关于你的第二个问题，要理解这个函数, you need to understand divide and conquer method. In quick sort, for n items if you take the last value as pivot, the number of items will decrease by 1, which will reduce the number of items to (n-1), Now if you recursively call quick sort taking last value as pivot, each time one item will be reduced. Thus the complexity will be ，以中间值为基准则不是这样

Answer 2

这里得到这个我将通过 O 解决 T(n-1)+O(N) 我的意思是 theta 所以令 m=2^n 以便 log(m)=n

现在声明一个新函数 S(m)=T(log m)

现在让我们说

S(m)=S(m/2)+log(m)

现在你同意S(m/2)+log(m)等于T(n-1)+n吗？

因为如果 m=2^n 所以 m/2=2^(n-1) 所以 log m(n-1) 我们已经确定 logm=(n)

所以现在我们已经建立了 S(m/2)+log(m)=T(n-1)+n 让我们解决 S(m/2)+log(m) 与主定理将在扩展案例 2 的帮助下得到 press the link to see it 所以如果我们遵循它，我们得到 log2(1)=0 并且当 k 为 1 时 f(m)=logm=O(logm)=O((n^0)*logm) 因此我们得到 S(m)=O(log^2 m) 或 O(n^2) 已知是快速排序的最坏情况