計算形成算法遞歸關係的步驟

Question

我是新算法分析的東西。我剛剛寫了一個分而治之的算法，它應該在O（n）時間內從一個數組中找到一個最大數，並且我堅持要形成它的遞歸。

以下是我的算法。

int findMax(int *A, int S, int E){ 

    if(S == E){  //1 unit of time 
     return A[S]; 
    } 
    else if(S == (E-1)){ // 1 unit of time 
     if(A[S] > A[E]){ // 1 unit of time 
      return A[S]; 
     } 
     else{ 
      return A[E]; 
     } 
    } 

    mid = (S+E)/2;   // 1 unit of time  
    L = findMax(A, S, mid); 
    R = findMax(A, mid+1, E); // 1 unit of time 

    if(L > R){   // 1 unit of time 
     return L; 
    } 
    else if(R > L){  // 1 unit of time 
     return R; 
    } 

} 

如果我錯了，請讓我糾正。我形成

復發是：

T（N）= 2T（N/2）+7

我是正確加起來所有單位成本7？

請幫我解決這個問題。謝謝。

Answer 1

首先，並非所有的代碼路徑返回，讓我們修改了算法的最後一個if/else語句如下：

if(L > R){   // 1 unit of time 
    return L; 
} 
else {  // 1 unit of time 
    return R; 
} 

• T(1) = 1：這只是使第一比較成功。
• T(2) = 3：這將進行三次比較以找出兩個項目的最大值。
• T(N) = 2*T(N/2) + 4, for N > 2

最後一個是如下：

+1 for first if comparison, which will fail 
+1 for the else if part of the first comparison block, which will also fail 
+1 for computing the middle element 
+2*T(N/2) for the recursive parts 
+1 for the last comparison (single if)