Complexitatea algoritmilor: timp, memorie și Big O

Complexitatea descrie cum crește necesarul de operații sau memorie când crește dimensiunea intrării. Notația O exprimă o limită asimptotică superioară, nu un timp exact în secunde. Un algoritm O(n) poate fi mai lent pentru intrări mici decât altul O(n log n), din cauza constantelor și implementării.

Analiza pornește de la ce reprezintă n. Într-un graf avem de obicei două dimensiuni, vârfuri și muchii. Într-o matrice dreptunghiulară avem linii și coloane. Înlocuirea lor cu o singură literă fără explicație poate ascunde costul real.

Cum funcționează

O operație pe un tip numeric fix este tratată de obicei ca O(1). O parcurgere a n valori are cost O(n). Două bucle imbricate care parcurg fiecare n valori au O(n²). Două bucle consecutive au în schimb O(n)+O(n)=O(n), deoarece costurile se adună, nu se înmulțesc.

O buclă care înjumătățește dimensiunea la fiecare pas are O(log n) iterații. Dar un algoritm recursiv care vizitează ambele jumătăți nu are automat timp logaritmic: trebuie să aduni costurile tuturor apelurilor. În merge sort, fiecare nivel prelucrează în total n elemente, iar numărul nivelurilor este logaritmic, deci timpul este O(n log n).

Analiza memoriei distinge datele de intrare, rezultatul și spațiul suplimentar. Un algoritm care calculează suma unui vector folosește un acumulator O(1), chiar dacă vectorul însuși ocupă O(n). Recursia consumă memoria apelurilor active; nu numărul total de apeluri este întotdeauna cel care determină vârful de memorie.

Cazul cel mai rău, cazul mediu și costul amortizat sunt concepte diferite. Pentru căutarea liniară, primul element poate fi găsit imediat, dar o valoare absentă cere examinarea întregului vector. Nu deduce complexitatea generală dintr-o singură rulare favorabilă.

Exemplu urmărit pas cu pas

Programul numără perechile de indici i<=j pentru n între zero și 10000. Pentru n=4, prima iterație exterioară produce patru perechi, apoi trei, două și una: în total zece. Numărul operațiilor este n+(n-1)+...+1=n(n+1)/2, deci crește pătratic.

Dublarea lui n duce aproximativ la de patru ori mai multă muncă pentru termenul dominant. Factorul 1/2 nu schimbă clasa O(n²), dar poate conta în măsurători concrete. Calcularea directă a formulei ar avea cost constant în modelul cu întregi de dimensiune fixă.

Implementare C++17

#include <iostream>
int main() {
    int n;
    std::cin >> n;
    long long total = 0;
    for (int i = 0; i < n; ++i)
        for (int j = i; j < n; ++j)
            ++total;
    std::cout << total << '\n';
}

De ce funcționează și cât costă

Fiecare valoare a lui i produce exact n-i iterații interioare. Adunarea acestor costuri este justificată fiindcă buclele execută toate aceste cazuri, fără oprire anticipată. Formula sumei aritmetice oferă numărul exact pentru acest exemplu.

Timpul programului este O(n²), iar memoria suplimentară O(1). Numărarea folosește long long. Pentru o soluție reală, verifică atât numărul operațiilor, cât și accesul la memorie și costul intrării/ieșirii.

Greșeli frecvente

Nu transforma automat fiecare pereche de bucle în O(n²): limitele pot fi diferite sau un indice poate avansa global o singură dată. Nu confunda limita asimptotică cu o promisiune de încadrare în orice limită de timp.

Exersează

Compară două parcurgeri consecutive de n elemente cu două parcurgeri imbricate. Ce se întâmplă aproximativ când dublezi n?

Rezolvare explicată: Cele consecutive fac aproximativ 2n pași, deci munca se dublează. Cele imbricate fac aproximativ n² pași, deci munca se multiplică aproximativ cu patru.

Continuă să înveți

Căutare, divide et impera și parcurgeri de graf.

Întrebări frecvente

Ce înseamnă O(1)?

Costul nu crește cu dimensiunea intrării în modelul analizat. Nu înseamnă neapărat o singură instrucțiune sau un timp identic pe toate calculatoarele.

Două bucle înseamnă întotdeauna O(n²)?

Nu. Contează dacă sunt consecutive sau imbricate și câte iterații execută efectiv. Analizează limitele, nu doar aspectul codului.

De ce ignorăm constantele în Big O?

Notația urmărește ritmul de creștere pentru intrări mari. Constantele rămân relevante practic, dar nu diferențiază clasele asimptotice de bază.

Cum analizez memoria recursiei?

Urmărești numărul maxim de apeluri simultan active și memoria fiecărui apel. Apelurile executate succesiv nu ocupă toate stiva în același timp.

Este O(n log n) mereu suficient?

Nu există o garanție universală. Depinde de valoarea maximă a lui n, constante, memorie, limbaj și limitele concrete ale evaluatorului.