Zählschritte, um eine Wiederholungsbeziehung eines Algorithmus zu bilden

Question

Ich bin neu in Sachen Algorithmenanalyse. Ich habe gerade einen Divide and Conquer-Algorithmus geschrieben, der in O (n) -Zeit eine maximale Zahl von einem Array finden soll, und ich bin dabei, seine Wiederholung zu bilden.

Folgendes ist mein Algorithmus.

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

} 

Bitte korrigieren Sie mich, wenn ich falsch liege.

Rezidive, die ich gebildet ist:

T (n) = 2T (n/2) +7

Bin ich alle Einheiten 7 kosten korrekt addieren?

Bitte helfen Sie mir damit. Vielen Dank.

Answer 1

Zunächst einmal nicht alle Codepfade zurückkehren, lassen Sie sich den Algorithmus ändert letzte if/else-Anweisung wie folgt:

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

• T(1) = 1: Das macht nur den ersten Vergleich und erfolgreich ist.
• T(2) = 3: Dies wird drei Vergleiche zu finden, um das Maximum von zwei Elementen zu finden.
• T(N) = 2*T(N/2) + 4, for N > 2

Der letzte ist wie folgt:

+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)