Program Algoritmul 1 suma max

Algoritmul 1 suma_max.cpp

int suma_max(int v[],int n)

T(n)=c1+n*c2+(n-1)c3+c4∑ti +c5[(n-1)-∑ti]+c6+n*c7+(n-1)c8+c9∑vi

∑ti =nr de aparitii a instructiunii cu costul c4

∑vi=nr de aparitii a instructiunii cu costul c9

c4- atribuire

c5-adunare si atribuire =>c5>c4

a)toate operatiile

Cazul cel mai favorabil

∑ti=n-1

∑vi=0

T(n)=c1+n*c2+(n-1)c3+(n-1)c4+c6+n*c7 +(n-1)c8

T(n)=n(c2+c3+c4+c7+c8)+(c1+c6-c3-c4-c8) O(n)

Cazul cel mai defavorabil

∑ti=0

∑vi=(n-1)

T(n)=c1+n*c2+(n-1)c3+(n-1)c5+c6+n*c7+(n-1)c8+(n-1)c9

T(n)=n(c2+c3+c5+c7+c8+c9)+(c1-c3-c5+c6-c8-c9) O(n)

3) Cazul mediu

∑ti=(n-1)/2

∑vi=(n-1)/2

T(n)=c1+n*c2+(n-1)c3+(n-1)/2*c4+(n-1)/2*c5+c6+n*c7+(n-1)c8+(n-1)/2 *c9

T(n)=n(c2+c3+c4/2+c5/2+c7+c8+c9/2)+(c1-c3-c4/2-c5/2+c6-c8-c9/2) O(n)

b) operatiile critice

1) Cazul cel mai favorabil

∑ti=n-1

∑vi=0

Secventa de operatii critice:2, 3,4,7,8

T(n)=n*c2+(n-1)c3+(n-1)c4+n*c7 +(n-1)c8

T(n)=n(c2+c3+c4+c7+c8)+(-c3-c4-c8) O(n)

2) Cazul cel mai defavorabil

∑ti=0

∑vi=n-1

Secventa de operatii critice: 2,3,5,7,8,9

T(n)=n*c2+(n-1)c3+(n-1)c5+c6+n*c7+(n-1)c8+(n-1)c9

T(n)=n(c2+c3+c5+c7+c8+c9)+(-c3-c5-c8-c9) O(n)

3) Cazul mediu

∑ti=(n-1)/2

∑vi=(n-1)/2

Secventa de operatii critice: 2,3,4,5,7,8,9

T(n)=n*c2+(n-1)c3+(n-1)/2*c4+(n-1)/2*c5+c6+n*c7+(n-1)c8+(n-1)/2 *c9

T(n)=n(c2+c3+c4/2+c5/2+c7+c8+c9/2)+(-c3-c4/2-c5/2-c8-c9/2) O(n)

Algoritmul 2 suma_max2.cpp

int suma_max2 (int v[],int n)

1.

}

return max;

}

T(n)=1+[2+ki+(2 +uj)]

ki=nr de repetari ale instructunii 4. ki

uj=nr de repetari ale instructiunii 7 uj

T(n)=1+2*(n-1)+ ki +uj+(n-i-1)*2

=1+2*(n-1)+ ki +uj +2*

=1+2*(n-1)+2*(n-1)n/2+ ki +uj=

=1+2*(n-1)+n(n-1)+ + ki +uj O(n)

Algoritmul 3 suma_max3.cpp

int suma_max3(int v[],int n)

return max;

}

T(n)=1+(1+1 + 1 +ui)=1+(2+ui+k)= 1+(2+ui+k)(n-k+1) =1+(2n-2k+2+(n-k+1)ui+nk-k+k) O(n)