Lucrare de laborator nr. 1 - Analiza algoritmilor (Timpul de execuţie al 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 NOTE DE CURS 1. Timpul de execuţie al algoritmilor. 2. Ordin de creştere 2.1. Notaţii asimptotice. 2.2. Operaţii asupra funcţiilor asimptotice 3. Etapele analizei complexităţii 4. Analiza empirică a complexităţii algoritmilor 5. Exemple 6. Numerele lui Fibonacci SARCINA DE BAZĂ: 1. Efectuaţi analiza empirică a algoritmilor propuşi în paragraful 6. 2. Determinaţi relaţia ce determină complexitatea temporală pentru aceşti algoritmi. 3. Determinaţi complexitatea asimptotică a algoritmilor. 4. Faceţi o concluzie asupra lucrării efectuate. Întrebări de control: 1. Enumeraţi factorii ce influenţează timpul de execuţie al algoritmului. 2. Când timpul de execuţie al algoritmului este dat de o relaţie de recurenţă ? 3. Care sunt regulile generale pentru evaluarea timpului de execuţie? 4. Care sunt etapele analizei empirice şi în care cazuri se face analiza empirică a algoritmilor? 5. Ce proprietăţi posedă funcţiile asimptotice?