アルゴリズムの反復関係を作るための計算ステップ

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

} 

私が間違っている場合は、私に修正してください。

iが形成された再発である：

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：これにより、3つの比較が行われ、最大2つのアイテムが見つかります。
• 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)