Informatică Algoritmi
Ce este complexitatea algoritmilor?
Complexitatea algoritmilor măsoară resursele necesare unui algoritm, precum timpul și memoria, în funcție de dimensiunea datelor de intrare. Ajută la alegerea celei mai bune soluții.
Tipuri de complexitate
- Complexitate temporală Timpul de execuție, exprimat ca O(n), O(n²). Exemplu: sortarea rapidă are O(n log n) în medie.
- Complexitate spațială Memoria utilizată, de exemplu O(1) pentru sortarea în loc, O(n) pentru un vector auxiliar.
- Cazul mediu și cel mai rău Sortarea prin inserție are O(n²) în cel mai rău caz, dar O(n) în cel mai bun.
De ce este importantă
- Scalabilitate Un algoritm O(n) funcționează bine și pentru milioane de date, spre deosebire de O(n²).
- Optimizare Identifică îmbunătățiri, ca trecerea de la O(n²) la O(n log n) în sortare.
- Comparație Permite alegerea între algoritmi: căutarea binară O(log n) vs. liniară O(n).
Analizează complexitatea înainte de implementare pentru a evita probleme la date mari.