Complexitatea algoritmilor

Două metode pot da același răspuns și totuși să folosească resurse diferite. Timpul unui algoritm poate fi estimat prin numărul de operații importante în funcție de mărimea intrării $n$; memoria prin spațiul suplimentar cerut. Dacă parcurgi un vector cu $n$ elemente o singură dată, numărul de verificări crește aproximativ odată cu $n$. Dacă pentru fiecare element îl compari cu toate celelalte, numărul poate crește aproximativ ca $n^2$.

Pentru 5 elemente, o parcurgere face 5 verificări; două bucle complete imbricate fac $5\cdot 5=25$ comparații. Pentru 10 elemente, cifrele devin 10 și 100. Compararea are sens doar după ce ambele metode sunt corecte și rezolvă aceeași problemă.

În Python, parcurgerea listei [4,7,2] verifică trei elemente; dacă lista are de două ori mai multe valori, aceeași buclă face de două ori mai multe verificări.

Complexitatea unui algoritm măsoară resursele folosite în funcție de mărimea $n$ a intrării. Timpul se estimează prin numărul de operații elementare (comparații, adunări, atribuiri) efectuate în cel mai defavorabil caz, iar memoria prin spațiul suplimentar cerut, în afara celui ocupat de date. Notația $O(f(n))$ exprimă un ordin de creștere: $O(n)$ înseamnă că numărul de operații crește proporțional cu $n$, $O(n^2)$ că se înmulțește cu 4 când $n$ se dublează, $O(\log n)$ că crește cu o unitate când $n$ se dublează. Notația ignoră constantele și termenii mai mici: $3n+5$ este $O(n)$, iar $n^2+n$ este $O(n^2)$. Ea nu dă durata în secunde, ci compară algoritmi care rezolvă aceeași problemă.

Exemplul 1 — căutarea secvențială. Se caută o valoare într-un vector cu $n$ elemente, parcurgând de la început. În cazul cel mai defavorabil, valoarea este pe ultima poziție sau lipsește, deci se fac $n$ comparații. Pentru $n=8$ sunt cel mult 8 comparații, iar dacă $n$ se dublează la 16, numărul lor se dublează: complexitatea de timp este $O(n)$, iar memoria suplimentară este constantă, $O(1)$.

Exemplul 2 — perechile de elemente. Pentru a compara fiecare element cu toate cele de după el se folosesc două cicluri imbricate:

#include <iostream>
using namespace std;
int main() {
    int n = 100, c = 0;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            ++c;
    cout << c;
    return 0;
}

Programul afișează 4950, adică $\frac{n(n-1)}{2}=\frac{100\cdot 99}{2}$. Numărul perechilor este aproximativ $n^2/2$, deci complexitatea este $O(n^2)$. Dacă $n$ crește de 10 ori, la 1000, numărul perechilor este 499 500, adică de aproximativ 100 de ori mai mare.

Exemplul 3 — înjumătățirea. Un ciclu care înjumătățește la fiecare pas valoarea lui $n$ până ajunge la 1 face aproximativ ${\log }_{2}n$ pași.

int n = 1000, pasi = 0;
while (n > 1) {
    n /= 2;
    ++pasi;
}
cout << pasi;

Valorile lui $n$ sunt 500, 250, 125, 62, 31, 15, 7, 3, 1, deci secvența afișează 9. Pentru $n=2^{20}$, adică peste un milion, ar fi 20 de pași. De aceea căutarea binară într-un vector ordonat, care înjumătățește intervalul, are complexitatea $O(\log n)$.

Pentru a vedea diferența dintre ordine, compară numărul de operații pentru trei mărimi ale intrării. La $n=10$ un algoritm $O(n)$ face aproximativ 10 operații, unul $O(n^2)$ aproximativ 100, iar unul $O(\log n)$ aproximativ 3 sau 4. La $n=1000$ cifrele devin aproximativ 1000, un milion și 10. La $n=1000000$ algoritmul pătratic ajunge la o mie de miliarde de operații, pe când cel logaritmic face doar aproximativ 20.

Comparația dintre metode are sens numai dacă ambele sunt corecte. Un algoritm mai lent poate fi preferabil când intrările sunt mici sau când este mai simplu și mai sigur; criteriul se alege după limitele din enunț.

Cel mai bun caz și cel mai defavorabil caz pot diferi: la căutarea secvențială, o valoare aflată pe prima poziție se găsește după o singură comparație, dar $O(n)$ descrie cazul defavorabil. De aceea o problemă trebuie să precizeze la ce caz se referă complexitatea cerută.

Numără pașii efectivi, nu deduce complexitatea numai din numărul de instrucțiuni scrise. O buclă de la 1 la $n$ cu o operație în interior este liniară. Două bucle imbricate cu limite $n$ dau ordin pătratic; două bucle consecutive de câte $n$ pași rămân liniare. Pentru $n=100$, două parcurgeri separate înseamnă aproximativ 200 de pași, iar imbricarea completă aproximativ 10 000. Când limita ciclului interior depinde de cel exterior, numărul execuțiilor este o sumă: $1+2+\dots +n=\frac{n(n+1)}{2}$. Un ciclu în care variabila se dublează la fiecare pas (i *= 2) sau se înjumătățește (n /= 2) face aproximativ ${\log }_{2}n$ pași, nu $n$. Dacă instrucțiunile din interiorul ciclurilor sunt simple și nu apar apeluri de funcții, numărul de operații se obține înmulțind numerele de execuții ale ciclurilor imbricate.

Exemplu în formatul examenului. Ce se afișează în urma executării secvenței de mai jos?

int c = 0;
for (int i = 1; i <= 5; i++)
    for (int j = i; j <= 5; j++)
        c++;
cout << c;

• a) 10
• b) 15
• c) 20
• d) 25

Răspunsul corect este b). Pentru $i=1$ ciclul interior se execută pentru $j=1,\dots ,5$, adică de 5 ori; pentru $i=2$ de 4 ori; apoi de 3, 2 și 1 ori. Suma este $5+4+3+2+1=15$. Varianta d) ar rezulta dacă ciclul interior ar începe mereu de la 1, iar varianta a) numără numai perechile cu $j>i$.

Verifică estimarea pe o valoare mică: la for (i = 1; i <= n; i *= 2) cu $n=16$, variabila $i$ ia valorile 1, 2, 4, 8, 16, deci ciclul face 5 pași, adică ${\log }_{2}16+1$, nu 16.

Greșeli frecvente

• Greșit: $O(n)$ spune timpul exact în secunde.
  Corect: exprimă cum crește numărul de operații când intrarea crește.
• Greșit: două bucle scrise una după alta dau automat $O(n^2)$.
  Corect: costurile lor se adună și rămân $O(n)$ dacă fiecare este liniară.
• Greșit: memoria ocupată de intrare și memoria auxiliară sunt mereu aceeași măsură.
  Corect: precizează convenția folosită când compari spațiul algoritmilor.

Înainte și după