Forma examenului : Test practic
Test I(propus de prof. Emanuela Cerchez
I.
Scrieti textul urmator, utilizand
fontul Times New Roman CE, dimensiunile caracterelor fiind de 12. Salvat 15315o1423p i
documentul cu numele vostru in directorul ATESTAT de pe discul C:\
NOTATIA ASIMPTOTICA
Notam TA(n) timpul necesar executiei algoritmului A
DEFINITIE
Fie f:N R+* o functie arbitrara. Spunem ca algoritmul este de
ordinul lui f(n), notat O(f(n)), daca si numai daca exista c>0 si n0 N astfel incat TA(n) C f(n), " n n0.
PROPOZITIE
Daca 
, atunci
.
DEMONSTARTIE:
, " n
1.
Alegand 
si 
.
|
O(n) (liniar) |
O(log(n)) (logaritmic) |
O(n*log(n)) (log-liniar) |
O(n2) (patratic) |
O(2n) (exponential) |
O(n!) (factorial) |
Tabelul ilustreaza comportarea a cinci dintre cele mai inportante functii de complexitate
|
