Запись рекуррентного отношения для алгоритма сортировки

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 ; 
} 

Он также говорит, что я могу предположить, сортировка вставками пирамидальной сортировки и слияния являются Θ (n2), Θ (п § п) и Q (п). Вот что я нашел до сих пор: Я разделяю массив на три части. Первые две части составляют 1/4 исходных данных, а третья часть (половина) составляет 1/2 от данных. Так что прямо сейчас у меня есть T (n) = 2T (n/4) + T (n/2). Не знаете, куда идти отсюда. Любая помощь будет принята с благодарностью!

Answer 1

Как указывает Дэвид в своем комментарии, существует только один рекурсивный вызов в алгоритме. Таким образом, ваш рекуррентное соотношение выглядит следующим образом:

 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) 

Поскольку SampleSort на n элементов включает HeapSort на n/2 пунктов, который имеет лучший случай Ω((n/2) log (n/2)) = Ω(n log n), мы знаем, что

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