Informatică Algoritmi
Complexitatea algoritmilor O(n) explicatii
Complexitatea algoritmilor O(n) descrie timpul de execuție ca fiind direct proporțional cu dimensiunea datelor de intrare n. Ea indică o relație liniară între n și numărul de operații. Aceasta este eficientă pentru multe aplicații practice.
Ce înseamnă O(n)
- Definiție Notația O(n) arată că timpul de execuție crește liniar cu n. Dacă n se dublează, timpul se dublează aproximativ.
- Exemplu de algoritm Parcurgerea unei liste pentru a găsi un element: pentru n elemente, faci n comparații în cel mai rău caz.
- Formula T(n) = c * n, unde c este o constantă care reprezintă timpul per operație, iar T este timpul total.
Comparație cu alte complexități
- O(1) Timp constant, independent de n. Exemplu: accesul la un element dintr-un array prin index.
- O(n²) Timp pătratic, crește rapid cu n. Exemplu: Bubble Sort pe liste nesortate.
- O(log n) Timp logaritmic, crește încet. Exemplu: căutarea binară pe liste sortate.
Pentru a analiza un algoritm, numără operațiile dominante în funcție de n.