Informatică Algoritmi
Complexitatea algoritmilor notatia Big O explicata
Notația Big O descrie eficiența unui algoritm prin viteza de creștere a timpului de execuție sau a spațiului de memorie necesar pe măsură ce datele de intrare cresc. Ea arată comportamentul algoritmului în cel mai defavorabil caz, ignorând constantele și factorii mici. De exemplu, un algoritm cu complexitatea O(n) durează de 10 ori mai mult pentru 10 date de intrare decât pentru 1.
Exemple comune de complexități
- O(1) - constant Accesul la un element dintr-un array prin index: timpul nu depinde de mărimea array-ului.
- O(log n) - logaritmică Căutarea binară într-o listă sortată: la fiecare pas, numărul de elemente se înjumătățește.
- O(n) - liniară Parcurgerea unei liste pentru a găsi un element: timpul crește proporțional cu numărul de elemente.
- O(n²) - pătratică Sortarea prin selecție: pentru fiecare element, se compară cu toate celelalte.
Cum se analizează un algoritm
- 1 Identifică operația dominantă Numără de câte ori se execută cea mai costisitoare instrucțiune, cum ar fi o comparație sau o atribuire.
- 2 Exprimă în funcție de n Scrie numărul de execuții ca o funcție matematică de mărimea datelor de intrare n.
- 3 Simplifică folosind Big O Ignoră termenii de ordin inferior și constantele, păstrând doar cel mai rapid crescător.
Folosește Big O pentru a compara algoritmi și a alege cel mai eficient pentru problema ta.