algorithm - 为排序算法编写递归关系

Question

我目前正在学习递推关系。我可以解决它们并找出它们的界限，但我不太确定的是如何为特定算法提出递归关系。这是我书中的一个例子:

// Sort array A[] between indices p and r inclusive.

SampleSort (A, p, r) {

     // Base Case: use HeapSort
     //
     if (r - p < 12) {
        HeapSort(A, p, r) ;
     }


     //  Break the array into 1st quarter, 2nd quarter and second half
     //
     n = r - p + 1 ;        // number of items in A[p..r] inclusive
     q1 = p - 1 + n/4 ;     // end of 1st quarter
     q2 = q1 + n/4 ;        // end of 2nd quarter


     //  Sort each of the 3 pieces
     //  using SampleSort recursively, Insertion-Sort and Heap-Sort
     //
     SampleSort (A, p, q1) ;
     InsertionSort (A, q1 + 1, q2) ;
     HeapSort (A, q2 + 1, r) ;


     // Merge the 3 sorted arrays into 1 sorted array
     //
     Merge (A, p, q1, q2) ;     // Merge 1st & 2nd quarter
     Merge (A, p, q2, r) ;      // Merge 1st & 2nd halves

     return  ;
}

它还说我可以假设 InsertionSort、HeapSort 和 Merge 是 Θ(n2)、Θ(n log n) 和 Θ(n)。到目前为止，这是我想出的:我将数组分成三部分。前两 block 是原始数据的 1/4，第三 block (一半)是数据的 1/2。所以现在我有 T(n) = 2T(n/4) + T(n/2)。不知道从这里去哪里。任何帮助将不胜感激!

Answer 1

正如 David 在他的评论中指出的那样，算法中只有一个递归 调用。所以你的递归关系看起来像这样:

      SampleSort   InsertionSort        HeapSort         Merges
          |             |                  |               |
          v             v                  v               v
T(n) = T(n / 4) + O((n / 4)^2) + O((n / 2) log (n / 2)) + O(n)
     = T(n / 4) + O(n^2)

使用 Master theorem (Case 3) , 我们得出结论

T(n) = O(n^2)     (worst case)

因为 n 项上的 SampleSort 涉及 n/2 项上的 HeapSort，它有最好的情况 Ω((n/2) log (n/2)) = Ω(n log n)，我们知道

T(n) = Ω(n log n)  (best case)