Lecție-punte: complexitate O(1), O(n), O(n log n), O(n²)

Ideea-cheie

Nu te interesează secundele — calculatorul tău e mai rapid sau mai lent decât al juriului, iar secundele depind de mașină. Te interesează numărul de operații elementare pe care le face algoritmul, exprimat în funcție de mărimea intrării n. Asta măsoară notația „O mare": cum crește efortul când n crește.

Iată cele câteva clase pe care le vei întâlni în 99% din probleme, de la cea mai ieftină la cea mai scumpă:

• O(1) — constant: același număr de operații indiferent de n (ex. citești a[i], faci o adunare). Nu depinde deloc de cât de mare e șirul.
• O(log n) — logaritmic: la fiecare pas tai problema în jumătate (căutarea binară, deschiderea dicționarului la mijloc). Pentru n = 1.000.000, log n e în jur de 20. Crește atât de încet încât e aproape gratis.
• O(n) — liniar: parcurgi intrarea o dată (o singură buclă peste șir).
• O(n log n) — pragul sortărilor bune (std::sort): o parcurgere, dar multiplicată cu un factor logaritmic mic.
• O(n²) — pătratic: două bucle imbricate, compari fiecare element cu fiecare. Sare în aer pentru n mare.

Cum alegi

Există un singur criteriu practic, pe care îl folosesc toți olimpicii înainte să scrie cod:

1. Citește din enunț cât de mare poate fi n (de obicei e scris explicit: n ≤ 100.000).
2. Estimează numărul de operații pe care îl face soluția ta pentru acel n (substitui n în formula complexității).
3. Compară cu bugetul: un calculator de concurs face cam 10^8 operații pe secundă (o sută de milioane). Dacă limita e 1 secundă și estimarea ta depășește mult 10^8 — vei lua TLE (Time Limit Exceeded). Atunci ai nevoie de un algoritm mai bun.

Concret, pune numere în formule. Iată câte operații ies pentru fiecare clasă, la trei valori uzuale ale lui n:

Cum citești tabelul față de bugetul de 10^8 operații pe secundă:

• O(n) și O(n log n): chiar și la n = 1.000.000 rămân sub sau în jurul lui 10^8. Sigur intră în 1 secundă.
• O(n²) la n = 1.000: doar 10^6 operații — e ok, sub buget cu mult.
• O(n²) la n = 100.000: 10^10 operații. Asta e de o sută de ori peste buget — ar dura ~100 de secunde. TLE garantat.

Așa că regula de buzunar: dacă vezi n ≤ 1.000 (sau câteva mii), un algoritm O(n²) trece liniștit. Dacă vezi n ≤ 100.000 sau mai mult, O(n²) e mort din start — trebuie să cobori la O(n log n) (sortare) sau O(n).

Un exemplu de decizie. Problemă: „dat un șir de n numere, există două care se adună la S?"

• Soluția naivă: pentru fiecare pereche (i, j) verifici dacă a[i] + a[j] == S. Două bucle imbricate — O(n²).
• Dacă n ≤ 1.000: O(n²) = 10^6 operații. Scrie-o liniștit, e cea mai simplă.
• Dacă n ≤ 200.000: O(n²) = 4 × 10^10 — TLE. Sortezi șirul (O(n log n)) și folosești doi indici de la capete, sau cauți binar complementul. Estimarea de operații ți-a spus înainte să scrii cod că naiva nu e bună.

Iată cum arată cele două bucle care fac diferența între O(n) și O(n²):

#include <iostream>
using namespace std;

int main() {
    int n = 100000;
    long long operatii = 0;

    // O(n): o singura parcurgere -> n operatii
    for (int i = 0; i < n; i++) {
        operatii++;
    }
    // aici operatii == n == 100000 (sub buget)

    operatii = 0;
    // O(n^2): bucla in bucla -> n * n operatii
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            operatii++;          // se executa de n*n ori
        }
    }
    // aici operatii == 10000000000 (10^10) -> mult peste 10^8 -> TLE

    cout << operatii << "\n";
    return 0;
}

Diferența nu e în cod (ambele par „doar niște bucle") — e în câte operații se execută. Bucla dublă nu costă de două ori mai mult decât una simplă, ci de n ori mai mult.