algorithm - 随机快速排序递归深度

Question

我正在阅读 Algorithms Illuminated: Part 1 ，问题 5.3 指出:

Let ⍺ be some constant, independent of the input array length n, strictly between 0 and 1/2. Assume you achieve the approximately balanced splits from the preceding problem in every recursive call - so whenever a recursive call is given an array of length k, each of its two recursive calls is passed a subarray with length between ⍺k and (1 - ⍺)k. How many successive recursive calls can occur before triggering the base case? Equivalently, which levels of the algorithm’s recursion tree can contain leaves? Express your answer as a range of possible numbers d, from the minimum to the maximum number of recursive calls that might be needed. [Hint: The formula that relates logarithmic functions with different bases is log n = ln n]

答案选择:

1. -log(n)/log(⍺) <= d <= -log(n)/log(1 - ⍺)
2. 0 <= d <= -log(n)/log(⍺)
3. -log(n)/log(1 - ⍺) <= d <= -log(n)/log(⍺)
4. -log(n)/log(1 - 2⍺) <= d <= -log(n)/log(1 - ⍺)

我的分析:

如果⍺ < 1/2，则 1 - ⍺ > ⍺，则子数组长度为 (1 - ⍺)n 的分支将具有更大的递归深度。

n / (1 - ⍺)^d = 1
Taking log[base(1 - ⍺)] on both sides
log[base(1 - ⍺)](n) = d
By log rule
d = log(n)/log(1 - ⍺)

最好的情况应该是log(n)/log(⍺)，因此答案1似乎是正确的。但是，我对减号感到困惑；我不明白递归树的高度怎么可能是负数。另外，我希望有人能验证我的分析，如上所示。

有什么想法吗？

Answer 1

您的分析有一个小错误。

正确的方程是 n * (1 - ⍺) ^ d = 1 而不是 n/(1 - ⍺) ^ d = 1。这会添加您正在寻找的负号。

请记住 ⍺ 和 (1 - ⍺) 都小于 1。因此，对数是负数。在其上再添加一个负号会导致最小和最大深度的整体正值。