Algoritmi si programare ID

3x puncte

categorie: Informatica

nota: 9.55

nivel: Facultate

Complexitatile pentru cazul cel mai favorabil nu ofera informatii relevante despre e cienta algoritmului. Mult mai semni cative sunt informatiile oferite de complexitatile in cazul cel mai nefavorabil: in toate celelalte cazuri algoritmul va avea performante mai bune sau cel putin la fel de bune.Pentru complexitatea timp nu este necesar totdeauna sa numaram toate operatiile.

Pentru [...]
DOWNLOAD REFERAT

Preview referat: Algoritmi si programare ID

Complexitatile pentru cazul cel mai favorabil nu ofera informatii relevante despre e cienta algoritmului. Mult mai semni cative sunt informatiile oferite de complexitatile in cazul cel mai nefavorabil: in toate celelalte cazuri algoritmul va avea performante mai bune sau cel putin la fel de bune.Pentru complexitatea timp nu este necesar totdeauna sa numaram toate operatiile.

Pentru exemplul de mai sus, observam ca operatiile de atribuire (fara cea initiala) sunt precedate de comparatii. Astfel ca putem numara numai comparatiile, pentru ca numarul acestora domina numarul atribuirilor. Putem merge chiar mai departe si sa numaram numai comparatiile intre z si componentele tabloului. sfobs Exista situatii cand instantele p cu g(p) = n pentru care TA(p) este egala cu TA(n) sau ia valori foarte apropiate de TA(n) apar foarte rar.

Pentru aceste cazuri este preferabil sa calculam comportarea in medie 18 a algoritmului. Pentru a putea calcula comportarea in medie este necesar sa privim marimea TA(p) ca ind o variabila aleatoare (o experienta = executia algoritmului pentru o instanta p, valoarea experientei= durata executiei algoritmului pentru instanta p) si sa precizam legea de repartitie a acestei variabile aleatoare.

Apoi, comportarea in medie (complexitatea medie) se calculeaza ca ind media acestei variabile aleatoare (consideram numai cazul complexitatii tim.
DOWNLOAD REFERAT
« mai multe referate din Informatica

CAUTA REFERAT


TRIMITE REFERAT CERE REFERAT
Referatele si lucrarile oferite de E-referate.ro au scop educativ si orientativ pentru cercetare academica.