最大和快速排序

Question

的最小深度这是CLR的（算法导论）问题的问题去如下：

假设在快速排序的每一级的分裂是在比例1 - αα，其中， 0 <α≤1/2是一个常数。表明，在递归树中的叶的最小深度为大约 - LG N/LGα和最大深度为约-lg N/LG（1 - α）。 （不要担心整数四舍五入）。http://integrator-crimea.com/ddu0043.html

我没有得到如何实现这个解决方案。根据链接他们显示，对于1：9的比例，最大深度为log n/log（10/9）和最小log n/log（10）。那么如何证明上述公式呢？请帮助我，我刚刚遇到算法和数据结构课程，我该怎么去错。

Answer 1

首先，让我们考虑这个简单的问题。假设你有一个数字n和一个分数（在0和1之间）p。你需要将n乘以p乘以多少次以使结果数小于或等于1？

n*p^k <= 1 
log(n)+k*log(p) <= 0 
log(n) <= -k*log(p) 
k => -log(n)/log(p) 

现在，让我们考虑您的问题。假设您将两个片段中较短的片段发送给左侧的孩子，并将较长的片段发送给右侧的孩子。对于最左边的链，通过在上面的等式中用\ alpha代替p给出长度。对于最右边的链，通过用1 \α代替p来计算长度。这就是为什么你有这些数字作为答案。