Informatică Algoritmi
Complexitatea algoritmilor
Complexitatea algoritmilor măsoară resursele necesare, cum ar fi timpul (complexitate temporală) și memoria (complexitate spațială). Se exprimă folosind notația Big O, de exemplu O(n) pentru o buclă simplă. Aceasta ajută la compararea eficienței algoritmilor.
Tipuri de complexitate
- Constantă - O(1) Timpul de execuție nu depinde de dimensiunea inputului, cum ar fi accesul la un element dintr-un array.
- Liniară - O(n) Timpul crește proporțional cu n, ca în căutarea liniară printr-o listă.
- Pătratică - O(n^2) Timpul crește cu pătratul lui n, exemplu fiind Bubble Sort.
Calcularea complexității
- 1 Identificarea buclelor Numără buclele imbricate: o buclă simplă are O(n), două bucle imbricate au O(n^2).
- 2 Ignorarea constantelor În Big O, ignori termenii constanți și coeficienții, concentrându-te pe cea mai mare rată de creștere.
- 3 Exemplu: algoritm cu O(n log n) Mergesort are această complexitate datorită împărțirii recursive și îmbinării.
Analizează complexitatea înainte de a implementa un algoritm pentru a alege cea mai eficientă soluție.