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

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)。那么如何证明上述公式呢？由于我是算法和数据结构课程的新手，请帮助我找出问题所在。

- meteors

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-\alpha作为p代入计算得出的。这就是为什么您有那些数字作为答案。

- ElKamina

---

你能解释一下你是如何从 np^k <= 1 推导出 log(n)+klog(p) <= 0 的吗？ - andigor

对数（log）是一个严格递增的函数（即 x>y>0，log(x)>log(y)）。log(1)=0（等号右侧）。log(xy) = log(x) + log(y)，因此log(np^k) = log(n) + log(p^k)。log(x^y) = ylog(x)，因此log(p^k) = k*log(p)。 - ElKamina

Answer 2

一般问题和答案

假设快速排序每个级别的分割比例为1-α:α，其中0< α ≤1/2是一个常数。证明递归树中叶子节点的最小深度约为-lgn/lgα，最大深度约为-lgn/lg(1-α)。（不用担心整数四舍五入。）

答案：

最小深度遵循一条路径，始终采取分区的较小部分，即将元素数量乘以α。一次迭代将元素数量从n减少到αn，i次迭代将元素数量减少到(α^i)n。在叶子节点处，只剩下一个元素，因此在深度为m的最小深度叶子节点处，我们有(α^m)n=1。因此，αm=1/n。取对数，我们得到m*lgα=−lgn，或m=−lgn/lgα。 同样地，最大深度对应于始终采取分区的较大部分，即每次保留1−α的元素。当只剩下一个元素时，达到最大深度M，即[(1−α)^M ]n=1。因此，M=−lgn/lg(1−α)。 所有这些方程都是近似值，因为我们忽略了floor和ceiling。

来源

- المعتز بالله بني يونس