Lucrare de laborator Nr 1 la Analiza si Proiectarea Algoritmilor - Analiza si Proiectarea Algoritmilor

Extras din document

Scopul lucrării: 1. Analiza empirică a algoritmilor. 2. Analiza teoretică a algoritmilor. 3. Determinarea complexităţii temporale şi asimptotice a algoritmilor Consideratii teoretice: Numerele lui Fibonacci. Sirul lui Fibonacci este definit prin urmatoarea recurenta: Analiza matematică a complexităţii algoritmilor poate fi dificilă în cazul unor algoritmi care nu sunt simpli.O alternativă la analiza matematică a complexităţii o reprezintă analiza empirică. Etapele analizei empirice 1. Se stabileşte scopul analizei. 2. Se alege metrica de eficienţă ce va fi utilizată (număr de execuţii ale unei/unor operaţii sau timp de execuţie a întregului algoritm sau a unei porţiuni din algoritm. 3. Se stabilesc proprietăţile datelor de intrare în raport cu care se face analiza (dimensiunea datelor sau proprietăţi specifice). 4. Se implementează algoritmul într-un limbaj de programare. 5. Se generează mai multe seturi de date de intrare. 6. Se execută programul pentru fiecare set de date de intrare. 7. Se analizează datele obţinute. Pentru a efectua o analiză empirică nu este suficient un singur set de date de intrare ci mai multe, care să pună în evidenţă diferitele caracteristici ale algoritmului. Sarcina Executarea unui program in limbajul de programare C++ care va compara cele 3 metode expuse in materialul teoretic p-ru diferite valori ale lui n. Listingul programului: