尾递归快速排序的空间复杂度是多少?

Question

查看以下尾递归快速排序伪代码

QuickSort(A[1, ..., n], lo, hi)
Input: An array A of n distinct integers, the lower index and the higher index
// For the first call lo = 1 and hi = n
Output: The array A in sorted order
If lo = hi return
// The array A is already sorted in this case
If lo > hi or indices out of the range 1 to n then return
Else
Pick an index k in [lo,hi] as the pivot
// Assume that this can be done using O(1) cells on the stack
i = Partition(A[lo, ..., hi], k)
// Use in-place partitioning here so assume that this can be done
// using O(1) space on the stack
If i - lo <= hi - i
QuickSort(A, lo, i-1) // sort the smaller half first
QuickSort(A, i+1, hi)
Else
QuickSort(A, i+1, hi) // sort the smaller half first
QuickSort(A, lo, i-1)

假设每次我分析枢轴时都是对抗性选择的，它应该具有 O(logn( 的空间复杂度 [我不完全确定是否正确]，但是如果随机均匀选择枢轴，空间复杂度会受到怎样的影响？ 我对理解空间复杂性随时间复杂性相当陌生，因此任何反馈都值得赞赏！

Answer 1

请参阅这篇涵盖尾递归的文章

在文章中，它说尾递归快速排序的空间复杂度如下：

space complexity = input + O(log(n))

可以在下面找到一些文章来更深入地了解：

• 旋转以了解快速排序 Pt.1
• 旋转以了解快速排序 Pt.2
• 来自杜克大学的快速排序笔记
• 卡内基甜瓜随机快速排序讲义
• 快速排序的算法分析
• 使用随机旋转进行快速排序

Answer 2

时间的最坏情况是，如果尽可能不均匀地划分数组，则该时间将O(n^2)。 如果你不做尾递归，那也是空间最糟糕的情况。

但是，如果您不均匀地划分数组并执行尾递归排序，则对较大一半的排序的调用不会占用空间，因为您只是替换了当前的调用帧。 因此，使用的最大空间是当您一遍又一遍地进行第一次递归调用时。 这最多是1/2最多1/2...总共log_2(n)个呼叫帧。

如果您使用一致选择的枢轴从最坏情况切换到平均情况，则会再次O(log(n))，但常数更好。 首先，它不能超过这个数字，因为平均情况不能超过最坏的情况。

诀窍是证明你无法改善这个界限。 为了证明这一点，我们可以证明对大小n数组进行排序的平均空间至少为C log(n+1)/(3 log(2))其中C是单个调用的空间。

通过检查，n = 1, 2, ..., 7也是如此，因为初始调用占用空间C和log(n+1)/(3 log(2)) <= 1。

如果n大于 7 并且该语句在n之前为真，我们的枢轴会将我们分成大小为m和n-mm <= n-m的组。 至少在偶数的情况下，n <= 4m和我们在第一次递归调用期间的预期最大成本至少为

C 1 + f(m)
>= C  + f(n/4 rounded up)
>= C (3 log(2)) /(3 log(2))    + C log(n/4 + 1)/(3 log(2)))
>  C (3 log(2)                 + log(n+1) - 2 log(2)    ) / (3 log(2)) )
= C (log(n+1) + log(2)) / (3 log(2))

其余时间不成立，我们在尾递归调用期间的预期最大成本至少是

f(n-m)
>= f(n/2 rounded down)
>= C log(n/2 + 1/2) / (3 log(2)) # n/2
= C (log(n+1) - log(2)) / (3 log(2))

当您对这两者求平均值时，您将获得所需的C log(n+1) / (3 log(2))下限。

(我可能犯了一个小错误，但这个想法是正确的。