Подсчет шагов для формирования рекуррентного отношения алгоритма

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

} 

Пожалуйста, сделайте меня правильным, если я ошибаюсь.

Рецидив, что я образовавшийся:

Т (п) = 2T (п/2) +7

я правильно сложением все единицы стоят 7?

Пожалуйста, помогите мне с этим. Благодарю.

Answer 1

Прежде всего, не все пути кода возвращаются, давайте изменим алгоритм в прошлом, если/другое заявление следующим образом:

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)