我如何证明快速排序的主定理 [英] how can i prove the master theorem for quicksort

问题描述

我对算法quicksort有疑问.有人可以解释一下我如何得出结果(证明)2T(n/2)+Θ(n)吗?结果意味着:T(n-1)+Θ(n).

i have a question regarding the algorithm, quicksort. Can someone explain me how i get to the result (proof) 2T(n/2) + Θ(n) ? And what that result means : T(n-1) + Θ(n).

感谢所有答案.

推荐答案

主定理指出，

对于任何 ，

For any ,

1. 如果表示某些常量，然后.
2. 如果，然后.
3. 如果，用于某些常量，如果表示某些常量以及所有足够大的，然后

至于你的，
，

在这里，
(第二个条件)
因此，复杂度将为:

As for yours,
,

Here,
(2nd condition)
So the complexity will be:

对于第二个问题，请了解此功能，您需要了解分而治之的方法.快速排序，对于 n 个项目，如果您将最后一个值作为轴，则项目数将减少 1 ，这会将项目数减少至(n-1)，现在，如果您递归调用以最后一个值为支点的快速排序，则每次减少一项.因此，复杂度将为，当您将中间值作为枢轴时就不是这种情况.

For your second question, to understand this function , 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 , which is not the case when you take middle value as pivot.

这篇关于我如何证明快速排序的主定理的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！