Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Program Algoritmul 1 suma max

c

+ Font mai mare | - Font mai mic





DOCUMENTE SIMILARE

Trimite pe Messenger
Conversii de format in memorie
Operatori, operanzi, expresii
Accesul la biblioteca standard
Instructiunea For
Cauta maximul elementelor din lista
OPERATORI DE PRELUCRARE LA NIVEL DE BIT
Switch
INSTRUCTIUNI DE CICLARE: for, while, break
Tratarea erorilor -stderr si exit
Prezentarea generala a notiunii de limbaj de programare

TERMENI importanti pentru acest document

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)





Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 693
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2023 . All rights reserved

Distribuie URL

Adauga cod HTML in site