Proiectarea algoritmilor – complexitate

Analiza eficienței algoritmilor prin studiul complexității temporale și spațiale.

Ce măsurăm: complexitatea timp și complexitatea spațiu

Eficiența unui algoritm se judecă după două resurse:

• complexitatea timp — câte operații elementare (comparații, atribuiri, operații aritmetice) execută algoritmul, exprimate ca funcție de dimensiunea datelor de intrare n;
• complexitatea spațiu — câtă memorie suplimentară folosește, dincolo de datele de intrare.

De ce numărăm operații și nu secunde: timpul în secunde depinde de calculator, limbaj și compilator, pe când numărul de operații caracterizează algoritmul însuși. Această justificare se cere ca atare la teorie.

Pentru același algoritm, numărul de operații poate diferi la aceeași dimensiune n, în funcție de datele concrete; de aceea se disting:

• cazul favorabil — datele cele mai convenabile (la căutarea secvențială: elementul e chiar primul);
• cazul defavorabil — datele cele mai rele (elementul lipsește — se parcurge tot vectorul);
• cazul mediu — media pe toate intrările posibile.

Dacă nu se precizează altfel, complexitatea unui algoritm înseamnă comportarea în cazul defavorabil — garanția pe care o putem promite indiferent de date.

Există adesea un compromis timp-memorie: poți accelera un algoritm consumând memorie suplimentară (vectori de frecvență, tabele de programare dinamică, memoizare) sau poți economisi memorie cu prețul unor recalculări. Recunoașterea acestui compromis — de exemplu, de ce sortarea prin numărare e rapidă dar cere un vector auxiliar cât plaja valorilor — este exact genul de justificare punctată la subiectul de analiză.

Notația O — ordinul de complexitate

Notația O (O mare) exprimă ordinul de creștere al numărului de operații când n devine mare, ignorând constantele multiplicative și termenii de rang inferior: un algoritm cu 3n² + 20n + 7 operații este O(n²), pentru că la n mare termenul n² domină totul.

Ierarhia claselor uzuale, de la cea mai bună la cea mai slabă — trebuie știută pe de rost:

• O(1) — timp constant: accesul la un element de tablou prin indice;
• O(log n) — logaritmic: căutarea binară; dublarea lui n adaugă o singură operație;
• O(n) — liniar: parcurgerea unui vector, căutarea secvențială;
• O(n log n) — liniaritmic: MergeSort, HeapSort — pragul optim pentru sortările prin comparații;
• O(n²) — pătratic: două cicluri imbricate pe n, sortările elementare;
• O(2^n), O(n!) — exponențial, factorial: generarea submulțimilor, respectiv a permutărilor prin backtracking; impracticabile chiar pentru n de câteva zeci.

Cum citești complexitatea direct din structura codului:

• un ciclu de la 1 la n → O(n); două cicluri imbricate pe n → O(n²); trei → O(n³);
• două cicluri succesive (neimbricate) → O(n) + O(n) = tot O(n) — imbricarea, nu numărul ciclurilor, dă produsul; aceasta e confuzia clasică;
• un ciclu în care variabila se dublează sau se înjumătățește la fiecare pas (i = i * 2, n = n / 2) → O(log n);
• descompunerea unui număr în cifre → O(numărul de cifre) = O(log n).

Intuiția pe numere, bună la verificări rapide: pentru n = 1.000.000, log2(n) este aproximativ 20, n log n este aproximativ 20 de milioane (fezabil), iar n² este 10^12 (nefezabil pe timpul unui test).

Compararea algoritmilor: aceeași problemă, costuri diferite

Aceeași problemă admite adesea algoritmi cu ordine de complexitate radical diferite — iar subiectele cer explicit varianta eficientă.

Căutarea într-un vector: secvențială — O(n), merge pe orice vector; binară — O(log n), dar cere obligatoriu vector sortat. Aplicarea căutării binare pe vector nesortat dă rezultate greșite — condiția de aplicabilitate face parte din răspuns.

Verificarea primalității: testarea divizorilor până la n-1 este O(n); testarea doar până la radical din n este O(sqrt(n)) — argumentul: dacă n = a·b și a <= b, atunci a <= sqrt(n), deci orice număr compus are un divizor cel mult egal cu radicalul său.

Suma unui subșir de întrebări repetate: recalcularea fiecărei sume este O(n) per întrebare; cu sume parțiale precalculate (s[i] = suma primelor i elemente), fiecare întrebare costă O(1) — exemplu tipic de compromis timp-memorie.

Fibonacci: recursiv pur — exponențial; cu memorare sau iterativ — O(n).

Cel mai mare divizor comun: scăderi repetate — O(max(a, b)) în cazul defavorabil; algoritmul lui Euclid cu împărțiri — O(log(min(a, b))), pentru că restul cel puțin se înjumătățește la fiecare două împărțiri.

Regula practică pentru probleme de concurs și pentru subiectul III de BAC: estimezi n din enunț și alegi clasa de complexitate care încape. Pentru n de ordinul 10^5–10^6, algoritmii O(n²) sunt de regulă prea lenți; țintește O(n log n) sau O(n). Justificarea eficienței — de ce soluția ta nu parcurge de mai multe ori datele — este parte din punctaj, nu ornament.

Complexitatea algoritmilor de sortare

Sortările elementare, toate O(n²) în cazul defavorabil:

• selecție: la pasul i se caută minimul din zona nesortată și se aduce pe poziția i; face mereu același număr de comparații — aproximativ n²/2 — indiferent de date, dar cel mult n-1 interschimbări; complexitatea nu depinde de ordinea inițială;
• inserție: fiecare element nou se inserează la locul lui în zona deja sortată, deplasând elementele mai mari; pe vector deja sortat face doar n-1 comparații — O(n), cazul favorabil; pe vector sortat invers — O(n²);
• interschimbare (bubble sort): compară și schimbă perechi vecine în treceri repetate, până la o trecere fără nicio interschimbare; cu acest test de oprire, cazul favorabil (vector sortat) este O(n).

Sortările eficiente, O(n log n):

• MergeSort: Divide et Impera; garantat O(n log n) în orice caz, dar cere O(n) memorie suplimentară pentru interclasare; este sortare stabilă (păstrează ordinea relativă a elementelor egale);
• QuickSort: partiționare în jurul pivotului; O(n log n) în medie, dar O(n²) în cazul defavorabil (pivot mereu extrem — de exemplu vector deja sortat cu pivot primul element); în practică e printre cele mai rapide;
• HeapSort: construiește un heap și extrage repetat maximul; garantat O(n log n), memorie suplimentară O(1).

Rezultat teoretic cerut la grile: orice sortare bazată pe comparații face în cazul defavorabil cel puțin n log n comparații — nu există sortare prin comparații O(n).

Ocolirea acestei limite: sortarea prin numărare (count sort) nu compară elemente, ci numără aparițiile fiecărei valori într-un vector de frecvență — O(n + V), unde V este plaja valorilor; excelentă când valorile sunt mici (note, cifre, vârste), impracticabilă când plaja e uriașă. Condiția de aplicabilitate face parte din răspuns.

Test — 6 întrebări ca la examen