algorithm - 我怎样才能找到递归关系？

Question

如果我们想以 9:1 的比例划分子问题，如何找到描述快速排序成本的递归关系？

我正在寻找的快速排序算法如下:

Quicksort(A,p,r)
      if p<r then
         q<- partition(A,p,r)
         Quicksort(A,p,q-1)
         Quicksort(A,q+1,r)

Answer 1

Quicksort 使用随机选择的主元，因此很难保证比率接近 9:1，除非您尝试多个主元并在每个主元上花费线性时间以找出主元给出的比率。但是，我们假设您使用线性时间中值发现的确定性线性时间顺序统计泛化。那么，你的递归关系就是

T(n) = T(0.9*n) + T(0.1*n) + O(n)

仍将求解为 O(n log n)，但隐藏常数会更大。