Question

Ma poate ajuta cineva cu calculul complexitatii acestui algoritm si cu scrierea unei metode iterative a algoritmului??
Multumesc
ALG(m,n)
1. if m > n then
2. return ALG(m-n,n)
3. else
4. if n > m then
5. return ALG(n,m)
6. else
7. return n

Answer 1

Răspuns:

Complexitate: O(max(n,m))

Metoda iterativa:

void swap(int* a, int* b){

int cp = *a;

*a = *b;

*b = cp;

}

int alg(int m, int n){/*Prin scadere repetata*/

while(m!=n){

if(n>m){swap(&n,&m);}

else{m = m - n;}

}

return n;

}

Explicație:

Algoritmul respectiv este algoritmul pentru calcularea celui mai mare divizor comun prin metoda scaderii repetate.

Cel mai rau caz pentru acest algoritm este cand unul dintre paramteri este 1,

care se va scadea repetat din celalalt pana cand si celalalt ajunge la 1(conditia de terminare).

Astfel, daca n = 1 (complexitatea O(m)) sau m = 1(complexitatea O(n)).

In final, complexitatea este O(max(n,m)).