met*_*ors 4 sorting algorithm quicksort clrs data-structures
这是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).那么如何证明上述公式呢？因为我是算法和数据结构课程的新手,请帮助我在哪里出错.
首先,让我们考虑一下这个简单的问题.假设你有一个数字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来计算长度.这就是为什么你把这些数字作为答案.