Tematică științifică · 1.9
Analiza complexității
Timpul de execuție și operația de bază, ordinul de complexitate și tipurile de algoritmi, complexitatea structurilor repetitive, cele trei cazuri și spațiul de memorie utilizat.
Doi algoritmi corecți pentru aceeași problemă nu sunt neapărat la fel de eficienți.
Criteriile de eficiență sunt două: durata de executare și spațiul de memorie utilizat.
Măsurarea în secunde nu caracterizează algoritmul, ci calculatorul pe care a fost executat: același program se execută de zece ori mai repede pe alt procesor sau cu alt compilator. Se măsoară de aceea numărul de operații efectuate, în funcție de dimensiunea datelor de intrare. Acest număr nu depinde de calculator.
Operația de bază și timpul de execuție
Se numără de câte ori se execută operația de bază, în funcție de dimensiunea n a datelor de intrare.
| Algoritmul | Operația de bază |
|---|---|
| căutarea într-un vector | comparația dintre element și valoarea căutată |
| sortarea prin comparații | comparația dintre două elemente |
| înmulțirea a două matrice | înmulțirea a două numere |
| parcurgerea unui graf | vizitarea unui vârf sau a unei muchii |
Exemplu. La sortarea prin selecție, comparația v[j] < v[poz] se execută
(n − 1) + (n − 2) + … + 1 = n(n − 1)/2 = n²/2 − n/2 ori.
Ordinul de complexitate
Din expresia n²/2 − n/2 se păstrează numai n², deci ordinul de complexitate al sortării prin selecție este O(n²).
Din expresia timpului de execuție se elimină două categorii de termeni, din același motiv:
- constantele multiplicative — un calculator de două ori mai rapid înjumătățește timpul, dar nu schimbă modul în care acesta crește;
- termenii de ordin mai mic — pentru n = 1000, termenul n²/2 are valoarea 500 000, iar termenul n/2 are valoarea 500.
| Ordinul | Tipul algoritmului |
|---|---|
| O(1) | constant |
| O(log n) | logaritmic |
| O(n) | liniar |
| O(n log n) | liniar logaritmic |
| O(nᵐ) | polinomial; pentru m = 2 pătratic, pentru m = 3 cubic |
| O(kⁿ) | exponențial |
| O(n!) | factorial; crește mai repede decât orice funcție exponențială kⁿ (de exemplu, pentru n ≥ 3, 1·2·3·…·n > 2·2·…·2 = 2ⁿ⁻¹) |
Complexitatea structurilor repetitive
Ordinul de complexitate este dat de structurile repetitive care se execută în funcție de dimensiunea datelor de intrare. La structuri repetitive incluse una în alta, numărul de execuții este produsul numerelor de repetări ale fiecăreia.
| Structura | Numărul de execuții ale corpului | Ordinul |
|---|---|---|
for (i = 1; i <= n; i = i + k) | n/k | O(n) |
for (i = 1; i <= n; i = i * k) | log_k n | O(log n) |
for (i = n; i >= 1; i = i / k) | log_k n | O(log n) |
for (i = 1; i <= n; i++) cu for (j = 1; j <= n; j++) înăuntru | n · n | O(n²) |
for (i = 1; i <= n; i++) cu for (j = i; j <= n; j++) înăuntru | 1 + 2 + … + n = n(n+1)/2 | O(n²) |
Ultimul rând arată că o structură repetitivă interioară care pornește de la valoarea contorului exterior nu schimbă ordinul: suma 1 + 2 + … + n rămâne de ordinul n².
Ordinele de mărime
| Ordinul | n = 10 | n = 1000 | n = 10⁶ |
|---|---|---|---|
| O(1) | 1 | 1 | 1 |
| O(log n) | 3 | 10 | 20 |
| O(n) | 10 | 1 000 | 10⁶ |
| O(n log n) | 33 | 10 000 | 2 · 10⁷ |
| O(n²) | 100 | 10⁶ | 10¹² |
| O(n³) | 1 000 | 10⁹ | — |
| O(2ⁿ) | 1 024 | — | — |
| O(n!) | 3,6 · 10⁶ | — | — |
Pozițiile goale nu sunt o omisiune: valorile de acolo depășesc cu mult ce se poate calcula în timp util.
Un calculator obișnuit efectuează aproximativ 10⁸ operații elementare pe secundă. Din această valoare se poate deduce, pentru o limită de timp dată, ce ordin de complexitate este acceptabil.
| Dimensiunea datelor | Ordinul acceptabil |
|---|---|
| n ≤ 10 | O(n!) |
| n ≤ 25 | O(2ⁿ) |
| n ≤ 500 | O(n³) |
| n ≤ 10 000 | O(n²) |
| n ≤ 10⁶ | O(n log n) |
| n ≤ 10⁸ | O(n) |
Tabelul se citește și invers, iar în acest sens este mai util: din dimensiunea datelor precizată în enunț se deduce ce fel de algoritm trebuie căutat. Un enunț în care n ≤ 100 000 arată că o soluție pătratică nu se încadrează în timp.
Cele trei cazuri
Același algoritm poate efectua un număr foarte diferit de operații, în funcție de datele de intrare.
Materialul acesta se citește pe educamp.ro și nu se tipărește.
S-a încheiat minutul de citit liber.
Ce cuprinde subcapitolul
- Operația de bază și timpul de execuție
- Ordinul de complexitate
- Complexitatea structurilor repetitive
- Ordinele de mărime
- Cele trei cazuri
- Spațiul de memorie utilizat
- Compromisul dintre timp și memorie
- Exemplu de analiză completă
- Apariții la examen
Continuă lectura ca și cursant
Cel puțin un subcapitol din fiecare capitol este disponibil gratuit și integral. Pentru a citi toate celelalte subcapitole ale disciplinei, te înscrii la cursul de pregătire.
Te înscrii, alegi în cont când începe cursul și plătești prima lună prin transfer bancar. Pentru a vedea mai întâi cum este prezentată materia, poți reveni la primul subcapitol al capitolului.
Acces la suportul de curs
25 RON / lună, fără ședințe
Ce cuprinde:
- Acces la toate lecțiile disponibile
- Suport de curs pentru tematica științifică și metodică
- Exemple, explicații și exerciții
- Acces la materialele noi adăugate pe platformă
- Posibilitatea de a adresa întrebări
Poți alege și variante cu ședințe online, în grup sau individuale. Le vezi pe pagina cursului.
Ai întrebări sau o problemă? Scrie-mi pe WhatsApp, la 0745 874 576.
Surse (3)
- „Informatică. Manual pentru clasa a XI-a”, Editura Didactică și Pedagogică, București
- Cerchez, E., Șerban, M., „Programarea în limbajul C/C++ pentru liceu”, Editura Polirom, Iași, 2005
- Gheorghe, M. (coord.), Tătărâm, M., Achinca, C., Năstase, C., „Informatică. Manual pentru clasa a XI-a”, Editura Corint, București, 2008