Analiza algoritmilor - Apa

Extras din document

Analiza algoritmilor – Laborator 2  Determinarea complexitatii unui algoritm  Determinarea complexitatii unui algoritm recursiv  Metode de rezolvare a recurentelor de complexitate  Teme  Determinarea complexitatii unui algoritm Cum numaram pasii pe care ii executa un algoritm? recapitulare - masuram complexitatea ca pe o functie de dimensiunea datelor de intrare: T: N->R+ - pe parcursul acestui laborator, T(n) va reprezenta estimarea numarului de pasi pe care ii face algoritmul atunci cand dimensiunea datelor de intrare este n - de exemplu: pentru sortare, T(n) va estima numarul de pasi necesari sortarii unui vector de n elemente numararea este in general simpla pe algoritmi nerecursivi - ceea ce trebuie sa facem in general este sa identificam operatiile critice si sa vedem de cate ori se executa acestea - cand algoritmul este nerecursiv, pur si simplu il luam de la cap la coada si numaram operatiile critice, inmultim cand ele se afla intr-unul sau mai multe cicluri etc ceva mai dificil este cu algoritmii recursivi - nu este mereu clar sau usor de determinat cate apeluri recursive se executa