Trouver la relation de récurrence de cet algorithme?

Question

En supposant n = B-A + 1, je dois déduire la relation de récurrence de cet algorithme:

void recurringalgorithm(int *a, int A, int B){ 
    if (A == B){ 
    for (int j=0;j<B;j++){ 
     cout<<a[j]; 
    } 
    cout<<endl; 
    return; 
    } 
    for (int i=A;i<B;i++){ 
    dosomething(a[A],a[i]); 
    recurringalgorithm(a,A+1,B); 
    dosomething(a[A],a[i]); 
    } 
} 

aide?

Answer 1

Supposons que la complexité de votre algorithme récursif est h(A,B).

À partir de votre code, vous pouvez diviser h en 2 cas:

h(A,B) = { complexity-of-if-branch   if A = B 
     { complexity-of-rest-of-the-code otherwise 

La "complexité-de-si-branche" est trivial. Pour la "complexité du reste du code", puisqu'il implique recurringalgorithm, vous devrez à nouveau inclure h.

Par exemple, si la fonction est définie comme

function hh(A,B) { 
    for (var i = A+1; i < B; ++ i) 
     hh(i, B); 
} 

Ensuite, la complexité sera

hh(A,B) = hh(A+1, B) + hh(A+2, B) + ... + hh(B-1, B) 

Vous pouvez comparer avec votre code de généraliser.

(BTW, la complexité est h(A,B) = O(B * (B-A)!))