Complexitatea algoritmilor: O(n), O(n²), O(log n) pe înțeles

La BAC Informatică, complexitatea algoritmilor nu este un capitol de teorie pe care îl înveți separat și apoi îl uiți. Apare direct la ultima problemă din Subiectul III, unde ți se cere un algoritm „eficient din punctul de vedere al timpului de executare și al memoriei utilizate”, și indirect în grilele în care trebuie să spui de câte ori se execută o instrucțiune. Vestea bună: pentru nivelul de BAC îți trebuie doar câteva reguli simple și ochiul format să recunoască tiparele.

Ce înseamnă O(n), pe scurt

Complexitatea în timp descrie cum crește numărul de operații pe care le face un algoritm atunci când crește dimensiunea datelor de intrare, notată de obicei cu n (numărul de elemente dintr-un vector, numărul de valori din fișier, valoarea unui număr etc.). Nu ne interesează numărul exact de operații, ci ordinul de mărime.

Două reguli fac toată treaba:

• Păstrezi doar termenul dominant. Dacă un algoritm face 3n² + 5n + 7 operații, pentru n mare contează doar n².
• Ignori constantele. 2n și 100n sunt amândouă O(n): dacă dublezi n, timpul se dublează în ambele cazuri.

Așadar, când spui că un algoritm este O(n²), spui de fapt: „dacă datele cresc de 10 ori, timpul crește de aproximativ 100 de ori”.

Complexitățile pe care le întâlnești la BAC

Un calculator obișnuit face, orientativ, câteva sute de milioane de operații simple pe secundă. De aici vezi imediat de ce un algoritm O(n²) pe un milion de valori este inacceptabil, iar unul O(n) termină instantaneu.

Cum numeri operațiile: trei tipare

1. O buclă simplă

O structură pentru i←1,n execută cu un corp de lungime constantă face n pași, deci O(n). Contează doar câte ori se repetă, nu câte instrucțiuni are corpul.

2. Bucle imbricate

Iată un tipar clasic de grilă:

citește n
k ← 0
pentru i←1,n execută
    pentru j←i+1,n execută
        k ← k+1
scrie k

Pentru n = 5, bucla interioară se execută de 4, 3, 2, 1 și 0 ori, deci se afișează 10. În general, se afișează (n-1) + (n-2) + … + 1 = n(n-1)/2. Termenul dominant este n²/2, deci complexitatea este O(n²), chiar dacă bucla interioară nu merge mereu până la capăt.

3. Bucle care împart

citește n
i ← 1
cât timp i ≤ n execută
    i ← i*2

Variabila i ia valorile 1, 2, 4, 8, … Pentru n = 100 bucla se execută de 7 ori (i trece prin 1, 2, 4, 8, 16, 32, 64 și se oprește la 128). Numărul de pași este aproximativ log₂ n, deci O(log n). Același tipar apare la prelucrarea cifrelor unui număr: bucla cât timp n ≠ 0 execută n ← [n/10] se repetă de atâtea ori câte cifre are n, adică O(log n) în baza 10.

Cum alegi între două soluții: un exemplu complet

Să zicem că fișierul bac.in conține cel mult un milion de numere naturale, fiecare cel mult 1000. Trebuie să afișezi câte valori distincte sunt în fișier.

Soluția 1 (ineficientă). Memorezi toate numerele într-un vector și, pentru fiecare element, verifici dacă a mai apărut înainte. Pentru fiecare dintre cele n elemente parcurgi până la n elemente anterioare, deci O(n²) în timp. În plus, folosești un vector de un milion de elemente.

Soluția 2 (eficientă). Observi că valorile sunt mici (cel mult 1000). Folosești un vector de frecvență cu 1001 poziții: când citești x, verifici dacă frecv[x] este 0 (prima apariție) și apoi îl incrementezi. Fiecare număr este prelucrat o singură dată, deci O(n) în timp, iar memoria nu depinde de câte numere sunt în fișier.

#include <iostream>
#include <fstream>
using namespace std;

int frecv[1001];

int main()
{
    ifstream fin("bac.in");
    int x, distincte = 0;
    while (fin >> x)
    {
        if (frecv[x] == 0)
            distincte++;
        frecv[x]++;
    }
    cout << distincte;
    fin.close();
    return 0;
}

Pentru fișierul 5 3 5 1000 3 0 programul afișează 4 (valorile distincte sunt 0, 3, 5 și 1000).

Observă de unde vine eficiența: nu dintr-un truc de cod, ci din citirea atentă a restricțiilor. Faptul că valorile sunt cel mult 1000 este exact indiciul care îți spune că poți folosi un vector de frecvență.

Și memoria contează

Complexitatea în spațiu se judecă la fel: cât de multă memorie suplimentară folosești în funcție de n. Un algoritm care citește valorile una câte una și ține doar câteva variabile (suma, maximul, valoarea anterioară) are memorie O(1). Unul care memorează toate valorile într-un vector are memorie O(n). La problema de eficiență de la BAC, dacă poți rezolva cerința fără să păstrezi toate numerele, fă asta: citești cu while (fin >> x) și prelucrezi pe loc.

Cum scrii descrierea la itemul III.3.a

La primul punct al problemei de eficiență trebuie să descrii în limbaj natural metoda și să justifici de ce este eficientă. Nu ai nevoie de pagini întregi; trei-patru propoziții clare sunt suficiente. Pentru exemplul de mai sus:

„Se citesc pe rând numerele din fișier, fără a fi memorate. Se folosește un vector de frecvență indexat după valori (0…1000). La citirea unei valori x, dacă frecv[x] este 0, se incrementează numărul de valori distincte, apoi se incrementează frecv[x]. Algoritmul este eficient ca timp deoarece fiecare număr este prelucrat o singură dată (complexitate liniară) și ca memorie deoarece vectorul are dimensiune constantă, independentă de numărul de valori citite.”

Observă structura: ce faci, ce structuri de date folosești, de ce e rapid și de ce consumă puțină memorie. Dacă algoritmul tău nu e cel mai eficient posibil, de regulă poți obține totuși o parte din punctajul pentru program, dar pierzi punctele legate de eficiență, așa că merită să cauți soluția liniară.

Capcane frecvente

• Funcție apelată în buclă. O buclă de n pași care apelează la fiecare pas o funcție de verificare a primalității O(√n) are complexitatea totală O(n·√n), nu O(n).
• strlen în condiția buclei. for (i = 0; i < strlen(s); i++) recalculează lungimea la fiecare pas. Calculează lungimea o singură dată, înainte de buclă.
• Sortare inutilă. Dacă îți trebuie doar minimul și maximul, o parcurgere O(n) e mai bună decât o sortare.