Complexitatea Algoritmilor - Big O

Ce este Complexitatea?

Complexitatea măsoară cât de eficient este un algoritm în funcție de dimensiunea input-ului.

Notația Big O

Exprimă comportamentul asimptotic (pentru input mare).

Complexități Comune

Exemple

O(1) - Constantă

Copiază
1int acces(int v[], int i) {
2    return v[i];  // O(1)
3}

O(n) - Liniară

Copiază
1int suma(int v[], int n) {
2    int s = 0;
3    for (int i = 0; i < n; i++)  // O(n)
4        s += v[i];
5    return s;
6}

O(n²) - Pătratică

Copiază
1void bubble(int v[], int n) {
2    for (int i = 0; i < n; i++)        // O(n)
3        for (int j = 0; j < n-1; j++)  // O(n)
4            // ...                      // Total: O(n²)
5}

O(log n) - Logaritmică

Copiază
1int cautareBinara(int v[], int n, int x) {
2    int st = 0, dr = n-1;
3    while (st <= dr) {           // O(log n)
4        int mij = (st + dr) / 2;
5        if (v[mij] == x) return mij;
6        if (v[mij] < x) st = mij + 1;
7        else dr = mij - 1;
8    }
9    return -1;
10}

Reguli de Calcul

1. •Ignoră constantele: O(2n) = O(n)
2. •Păstrează termenul dominant: O(n² + n) = O(n²)
3. •Buclele nested se înmulțesc
4. •Buclele secvențiale se adună

Exerciții

1. •Ce complexitate are căutarea secvențială?
2. •Compară O(n log n) cu O(n²) pentru n = 1000
3. •Analizează complexitatea merge sort

---

Găsește un profesor de informatică pentru algoritmi avansați!