Structuri de Date 2023 - S1: Complexitate

Structuri de Date

Seminar 1

Cum masuram eficienta algoritmilor?

Benchmark? => masuram exact timpul sau spatiul necesar executarii algoritmului implementat.

Problema? Daca schimbam masina pe care ruleaza implementarea, poate spatiul necesar nu variaza, dar timpul masurat variaza conform specificatiilor calculatorului respectiv.

=> Avem nevoie de mecanisme pentru a determina eficienta algoritmilor care nu depind de masina pe care rulam algoritmul.

Metoda formala pentru determinarea eficientei nu este altceva decat numararea operatiilor necesare terminarii algoritmului.

Notatie: T(n) – timp de rulare al unui algoritm (in general masurat in nr. de comparatii sau de mutari/atribuiri)

Cazuri:

cel mai favorabil / best case
mediu / average case
cel mai nefavorabil / worst case (ofera o limita superioara a timpului de executare, avem certitudinea ca executarea algoritmului nu va dura mai mult)

Cel mai adesea se foloseste cazul cel mai nefavorabil si cel mediu pentru a descrie performanta unui algoritm.

Complexitatea asimptotica

Algoritmii se clasifica natural in clase de complexitate conform functiei T(n) care descrie numarul de operatii elementare.

De exemplu, pentru limita superioara a timpului T(n) a rularii unui algoritm, clasa de complexitate se determina eliminand factorii constanti din expresia T(n) si pastrand termenii cu cea mai rapida crestere.

Mai jos avem definitiile formale ale celor mai utilizate masuri ale complexitatii asimptotice.

Problema 1:

Determinati maximul dintr-un tablou de numere.

Numar comparatii?
Numar atribuiri?
- Best case?
- Worst case?

int largest(int arr[], int n){ int i; int max = arr[0];
for (i = 1; i < n; i++) if (arr[i] > max) max = arr[i]; return max;}

Problema 2:

Determinati diferenta dintre maximul si minimul dintr-un tablou de numere.

Numar comparatii?
Numar atribuiri?
- Best case?
- Worst case?

int difMinMax(int arr[], int n){ int i,start; if (n%2==0){ start = 2; if (arr[0]<arr[1]) {min=arr[0];max=arr[1];} else {max=arr[0];min=arr[1];} } else { start = 1; min=max=arr[0]; } for (i = start; i < n; i+=2) if (arr[i]<arr[i+1]){ if (arr[i]<min) min=arr[i]; if (arr[i+1]>max) max=arr[i+1]; } else { if (arr[i+1]<min) min=arr[i+1]; if (arr[i]>max) max=arr[i]; } return max-min;}

Problema 3:

Determinati daca un numar intreg dat este prim sau neprim.

n comparatii
n/2 comparatii
sqrt(n) comparatii
< sqrt(n)/2+1 comparatii

Atentie la verificarea complexitatii asimptotice a testului de primalitate. Nu e trivial 🙂

bool isPrime(int n){ if (n <= 1) return false; if (n==2) return true; if (n%2==0) return false; for (int i = 3; i <= sqrt(n); i+=2) if (n % i == 0) return false; return true;}

Problema 4:

Sa se gaseasca pozitia valorii x intr-un tablou de numere.

Numar comparatii?
- Best case?
- Worst case?

int search(int arr[], int n, int x){ int i; for (i = 0; i < n; i++) if (arr[i] == x) return i; return -1;}

Problema 5:

Sa se gaseasca pozitia valorii x intr-un tablou de numere sortate.

Numar comparatii?
- Best case?
- Worst case?

int binarySearch(int arr[], int l, int r, int x){ if (r >= l) { int mid = l + (r - l) / 2; // daca l-am gasit in mijloc if (arr[mid] == x) return mid; // daca x este mai mic decat mid, continuam in stanga if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // daca x este mai mare decat mid, continuam in dreapta return binarySearch(arr, mid + 1, r, x); } //n-a fost gasit return -1;}

Problema 6:

Sa se gaseasca pozitia valorii x intr-un tablou de numere sortate (si uniform distribuite).

Numar comparatii?
- Best case?
- Worst case?

int interpolationSearch(int arr[], int lo, int hi, int x){ // se cauta x intre indicii [lo, hi] in vector int pos; if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
pos = lo + (((double)(hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo])); // gasit? if (arr[pos] == x) return pos; // x este mai mare decat valoarea gasita, continuam cautarea in dreapta if (arr[pos] < x) return interpolationSearch(arr, pos + 1, hi, x); // x este mai mic decat valoarea gasita, continuam cautarea in stanga if (arr[pos] > x) return interpolationSearch(arr, lo, pos - 1, x); } //n-a fost gasit return -1;}