Analiza Complexității unui Algoritm 20

---

1. Obiectivele lecției:

• Să înțeleagă ce reprezintă complexitatea unui algoritm.
• Să învețe să analizeze și să determine complexitatea temporală și spațială a unui algoritm.
• Să aplice aceste concepte în probleme practice.

---

2. Conținutul lecției:

---

Ce este complexitatea unui algoritm?

• Definiție: Complexitatea unui algoritm este o măsură a resurselor consumate de algoritm, cum ar fi timpul de execuție și memoria utilizată, în funcție de dimensiunea intrării.
• Scop: Ajută la compararea algoritmilor și alegerea celui mai eficient pentru o problemă dată.

---

Tipuri de complexitate:

1. Complexitate temporală: Timpul necesar pentru a executa algoritmul.
2. Complexitate spațială: Memoria necesară pentru a executa algoritmul.

---

Notări comune:

• O-notation (Big O): Măsoară limita superioară a creșterii timpului/memoriei.
• Ω-notation (Omega): Măsoară limita inferioară a creșterii timpului/memoriei.
• Θ-notation (Theta): Măsoară rata exactă a creșterii timpului/memoriei.

---

3. Analiza complexității temporale:

---

Pasul 1: Identificarea operațiilor critice

Operațiile critice sunt cele care determină timpul total de execuție al algoritmului, cum ar fi comparațiile, atribuțiile sau iterațiile.

---

Pasul 2: Determinarea numărului de operații în funcție de intrare

1. Cazul cel mai favorabil (Best Case): Cel mai mic timp posibil de execuție.
2. Cazul cel mai defavorabil (Worst Case): Cel mai mare timp posibil de execuție.
3. Cazul mediu (Average Case): Timpul mediu de execuție.

---

Complexități comune:

1. O(1): Constantă – Timpul nu depinde de dimensiunea intrării.
   • Ex: Accesarea unui element dintr-un array.
2. O(log n): Logaritmică – Numărul de operații crește logaritmic.
   • Ex: Căutarea binară.
3. O(n): Liniară – Timpul crește proporțional cu dimensiunea intrării.
   • Ex: Căutarea secvențială.
4. O(n log n): Liniaro-logaritmică – Timpul este o combinație între liniar și logaritmic.
   • Ex: Merge Sort, Quick Sort (caz mediu).
5. O(n²): Cuadratică – Timpul crește proporțional cu pătratul dimensiunii intrării.
   • Ex: Sortarea prin bule.
6. O(2ⁿ): Exponențială – Timpul crește exponențial cu dimensiunea intrării.
   • Ex: Rezolvarea problemelor cu backtracking.

---

Exemplu: Sortarea prin bule

void bubbleSort(int arr[], int n) {

    for (int i = 0; i < n – 1; i++) {

        for (int j = 0; j < n – i – 1; j++) {

            if (arr[j] > arr[j + 1]) {

                int temp = arr[j];

                arr[j] = arr[j + 1];

                arr[j + 1] = temp;

            }

        }

    }

}

• Operații critice: Comparațiile din bucla interioară.
• Complexitate:
  • Caz favorabil: O(n) (dacă lista este deja sortată).
  • Caz defavorabil: O(n²) (dacă lista este ordonată invers).

---

4. Analiza complexității spațiale:

---

Memorie utilizată:

1. Memorie constantă (O(1)): Algoritmul folosește o cantitate fixă de memorie indiferent de intrare.
   • Ex: Căutarea secvențială.
2. Memorie liniară (O(n)): Memoria crește proporțional cu dimensiunea intrării.
   • Ex: Merge Sort.
3. Memorie exponențială (O(2ⁿ)): Algoritmul necesită memorie foarte mare pentru intrări mari.
   • Ex: Probleme de combinatorică sau de backtracking.

---

Exemplu: Merge Sort

void mergeSort(int arr[], int left, int right) {

    if (left < right) {

        int mid = left + (right – left) / 2;

        mergeSort(arr, left, mid);

        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);

    }

}

• Memorie suplimentară: O(n) pentru vectorii temporari utilizați la interclasare.
• Complexitate spațială totală: O(n).

---

5. Activități practice pentru elevi:

1. Determinați complexitatea unui algoritm dat pentru sortarea unui vector.
2. Scrieți un algoritm care parcurge un array și determinați complexitatea acestuia.
3. Implementați un algoritm de căutare și analizați complexitatea sa temporală și spațială.

---

6. Scheme logice pentru analiza unui algoritm:

1. Identificarea operațiilor critice:
   • Start -> Parcurgeți pas cu pas algoritmul -> Determinați operațiile repetitive -> Stop.
2. Evarea complexității:
   • Start -> Notați numărul de operații pentru fiecare secvență -> Stabiliți funcția de creștere -> Stop.

---

7. Concluzie:

• Analiza complexității unui algoritm este esențială pentru înțelegerea eficienței sale.
• Alegerea unui algoritm potrivit pentru o problemă specifică depinde de complexitatea sa temporală și spațială.
• Prin practică, elevii vor dezvolta abilități de analiză și optimizare a codului.