Informatică Algoritmi
Complexitatea algoritmilor O mare explicat
Notația O mare descrie limita superioară a timpului de execuție al unui algoritm, arătând cum crește cu dimensiunea datelor. Măsoară eficiența în cel mai rău caz.
Exemple comune
- O(1) - Timp constant Accesul la un element dintr-un vector prin index, indiferent de mărime.
- O(n) - Timp liniar Parcurgerea unei liste pentru a găsi un element, timpul crește proporțional cu n.
- O(n²) - Timp pătratic Sortarea prin selecție, cu două bucle imbricate, ineficient pentru date mari.
- O(log n) - Timp logaritmic Căutarea binară într-un vector sortat, timpul crește lent cu n.
Cum se calculează
- 1 Pasul 1: Identifică operația dominantă Numără de câte ori se execută cea mai frecventă operație, ca comparații în sortare.
- 2 Pasul 2: Exprimă în funcție de n Scrie formula, de exemplu T(n)=n²+3n pentru un algoritm cu buclă dublă.
- 3 Pasul 3: Ignoră termenii mici Păstrează cel mai mare termen: n²+3n devine O(n²), deoarece n² domină.
Folosește O mare pentru a compara algoritmi: O(log n) e mai bun decât O(n) pentru date mari.