algorithm - 快速排序的最大和最小深度

Question

这是一道CLR(Introduction to Algorithms)的题，题目如下:

假设快速排序每一级的拆分比例为 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)。那么如何证明上面的公式。请帮助我了解我哪里出错了，因为我是算法和数据结构类(class)的新手。

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)

现在，让我们考虑一下您的问题。假设您将两个片段中较短的一个发送给左 child ，将较长的发送给右 child 。对于最左边的链，长度是通过将\alpha 替换为上式中的 p 来给出的。对于最右边的链，长度是通过将 1-\alpha 替换为 p 来计算的。这就是您将这些数字作为答案的原因。