Eficienta algoritmilor

Eficienta unui algoritm este evaluata prin timpul necesar pentru executarea algoritmului.

Pentru a compara doi algoritmi care rezolva aceeasi problema,veti folosi aceeasi dimensiune a datelor de intrare si una dintre urmatoarele metode de evaluare a eficientei:numarul de operatii elementare ale algoritmului sau timpul mediu de executie.

Operatia de baza este o operatie elementara sau o succesiune de operatii elementare a caror executie nu depinde de valorile datelor de intrare.

Marimile care pot fi folosite in compararea a doi algoritmi sunt: eficienta si ordinul de complexitate.

Eficienta unui algoritm reprezinta timpul de calcul estimat prin numarul de executii ale operatiei de baza.

Ordinul de complexitate al unui algoritm il reprezinta timpul de calcul estimat prin ordinul de marime al numarului de executii ale operatiei de baza.

Tipuri de algoritmiOrdin de complexitate Tipul algoritmului

O(n) Algoritm liniar

O(nm) Algoritm polinomial.Daca m=2,algoritmul este patratic,iar daca m=3,algoritmul este cubic.

O(kn) Algoritm exponential.De exemplu,2n,3netc. Algoritmul de tip O(n!) este tot de tip exponential deoarece:1x2x…xn>2x2x2=2n-1.

O(logn) Algoritm logaritmic.

O(nlogn) Algoritm liniar logaritmic.

ConcluziiCei mai rapizi algoritmi sunt cei logaritmici.Daca pentru rezolvarea aceleiasi probleme

exista algoritmi polinomiali si exponentiali,se prefera cei polinomiali.

Daca pentru rezolvarea aceleiasi probleme exista mai multi algoritmi polinomiali,se prefera cel cu grad mai mic.

Sa se verifice daca intr-un vector sortat cu n elemente exista o valoare x citita de la tastatura. #include <iostream>

int n,a[50],x;int cauta (){ int s=0,d=n-1,m,gasit=0; while (!gasit&&s<=d) {m=(s+d)/2; if (a[m]==x) gasit=1; else if(a[m]<x) s=m+1; else d=m-1;} if (gasit) return 1;else return 0;}

int main (){ int i; cin>>n>>x; for(i=0;i<n;i++) {cout<<“a(“<<i+1<<“)=“;cin>>a[i];} if (caut()) cout <<“Elementul exista”; else cout <<“Elementul nu exista”;}