정렬 알고리즘에 대한 반복 관계 작성

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)가, Θ가와 Θ (N) (N 로그 n)하는 병합 수 있다고 말한다. 여기까지 제가 지금까지 생각해 냈습니다 : 배열을 세 조각으로 나눕니다. 첫 번째 두 조각은 원래 데이터의 1/4이며 세 번째 조각 (1/2)은 데이터의 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) 

SampleSortn의 항목 때문에이 최상의 경우 Ω((n/2) log (n/2)) = Ω(n log n)있다 HeapSortn/2에 대한 항목을 포함한다는 결론, 우리는

을 알고

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