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)。那么如何证明上述公式。由于我是算法和数据结构课程的新手，请帮助我了解我哪里出错了。

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)

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

Answer 2