Analiza complexitatii temporale si spatiale (Bac)

Analiza complexității temporale și spațiale este un domeniu fundamental al informaticii, care ne permite să evaluăm eficiența unui algoritm în funcție de resursele consumate: timp (numărul de operații elementare) și memorie (spațiul de stocare). Pentru Bacalaureat, este esențial să înțelegem notația asimptotică Big O, care descrie comportamentul unui algoritm atunci când dimensiunea datelor de intrare (n) tinde la infinit. Cele mai comune complexități sunt: O(1) – constantă, O(log n) – logaritmică, O(n) – liniară, O(n log n) – cvasi-liniară, O(n²) – pătratică, O(2ⁿ) – exponențială.

Complexitatea spațială se referă la memoria suplimentară folosită de algoritm (excluzând memoria pentru datele de intrare). De exemplu, un algoritm de sortare prin selecție are complexitate temporală O(n²) și spațială O(1) (nu folosește vectori auxiliari), în timp ce Merge Sort are O(n log n) temporal și O(n) spațial (necesită un vector temporar). În analiză, se iau în considerare cele mai defavorabile cazuri (worst-case), dar și cazul mediu.

Pentru exercițiile de Bac, se cere identificarea complexității unor secvențe de cod, adesea bucle imbricate sau recursivitate. Regula generală: pentru o buclă care se execută de n ori, complexitatea este O(n); pentru două bucle imbricate independente, O(n²); pentru o buclă care se reduce la jumătate la fiecare pas (divide et impera), O(log n). De asemenea, apelurile recursive simple, fără combinare, pot genera complexități exponențiale dacă numărul de apeluri crește rapid (ex: Fibonacci naiv O(2ⁿ)).

Înțelegerea acestor concepte ajută la alegerea celui mai potrivit algoritm pentru o problemă dată și la optimizarea codului.

Exemple

• Exemplul 1: Analiza unei bucle simple. Cod: for(i=0; i<n; i++) { a[i] = 0; }. Se execută o operație elementară (atribuire) de n ori, deci complexitatea temporală este O(n). Nu se alocă memorie suplimentară, deci complexitatea spațială este O(1).
• Exemplul 2: Bucle imbricate independente. Cod: for(i=0; i<n; i++) for(j=0; j<m; j++) { sum += i*j; }. Dacă n și m sunt independente, complexitatea este O(n*m). La Bac, de obicei m=n, deci O(n²). Spațial: O(1).
• Exemplul 3: Recursivitate – calculul factorial. int fact(int n) { if(n<=1) return 1; else return n * fact(n-1); }. Fiecare apel reduce n cu 1, deci numărul total de apeluri este n, complexitatea temporală O(n). Stiva de apeluri are adâncime maximă n, deci complexitatea spațială este O(n) (memorie pentru stivă).

Concepte cheie: Notația Big O, Analiza buclelor imbricate, Complexitatea spațială suplimentară