快速排序的最大和最小深度 [英] Maximum and minimum depth of quicksort

问题描述

这是CLR（算法简介）的问题，问题如下：

This was a problem of CLR (Introduction to Algorithms) The question goes as follow:

假设每个快速排序级别的拆分比例为1- α至α，其中0 ＜0。 α≤1/ 2是常数。证明递归树中叶子的最小深度约为-lg n / lgα，最大深度约为-lg n / lg（1-α）。 （不必担心整数舍入。） http://integrator-crimea.com/ddu0043.html

Suppose that the splits at every level of quicksort are in the proportion 1 - α to α, where 0 < α ≤ 1/2 is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately - lg n/ lg α and the maximum depth is approximately -lg n/ lg(1 - α). (Don't worry about integer round-off.)http://integrator-crimea.com/ddu0043.html

我不知道如何实现此解决方案。根据链接显示，对于1：9的比率，最大深度为log n / log（10/9），最小log n / log（10）。然后如何证明上述公式。首先，请让我了解算法和数据结构课程的最新知识。

I'm not getting how to reach this solution. as per the link they show that for a ratio of 1:9 the max depth is log n/log(10/9) and minimum log n/log(10). Then how can the above formula be proved. Please help me as to where am I going wrong as I'm new to Algorithms and Data Structures course.

推荐答案

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

First, let us consider this simple problem. Assume you a number n and a fraction (between 0 and 1) p. How many times do you need to multiply n with p so that resulting number is less than or equal to 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来计算长度。这就是为什么要用这些数字作为答案。

Now, let us consider your problem. Assume you send the shorter of the two segments to the left child and longer to the right child. For the left-most chain, the length is given by substituting \alpha as p in the above equation. For the right most chain, the length is calculated by substituting 1-\alpha as p. Which is why you have those numbers as answers.

这篇关于快速排序的最大和最小深度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！