Benchmark? => masuram exact timpul sau spatiul necesar executarii algoritmului implementat.
Problema? Daca schimbam masina pe care ruleaza implementarea, poate spatiul necesar nu variaza, dar timpul masurat variaza conform specificatiilor calculatorului respectiv.
=> Avem nevoie de mecanisme pentru a determina eficienta algoritmilor care nu depind de masina pe care rulam algoritmul.
Metoda formala pentru determinarea eficientei nu este altceva decat numararea operatiilor necesare terminarii algoritmului.
Notatie: T(n) – timp de rulare al unui algoritm (in general masurat in nr. de comparatii sau de mutari/atribuiri)
Cazuri:
cel mai favorabil / best case
mediu / average case
cel mai nefavorabil / worst case (ofera o limita superioara a timpului de executare, avem certitudinea ca executarea algoritmului nu va dura mai mult)
Cel mai adesea se foloseste cazul cel mai nefavorabil si cel mediu pentru a descrie performanta unui algoritm.
Algoritmii se clasifica natural in clase de complexitate conform functiei T(n) care descrie numarul de operatii elementare.
De exemplu, pentru limita superioara a timpului T(n) a rularii unui algoritm, clasa de complexitate se determina eliminand factorii constanti din expresia T(n) si pastrand termenii cu cea mai rapida crestere.
Mai jos avem definitiile formale ale celor mai utilizate masuri ale complexitatii asimptotice.
Problema 1:
Determinati maximul dintr-un tablou de numere.
Numar comparatii?
Numar atribuiri?
Best case?
Worst case?
Problema 2:
Determinati diferenta dintre maximul si minimul dintr-un tablou de numere.
Numar comparatii?
Numar atribuiri?
Best case?
Worst case?
Problema 3:
Determinati daca un numar intreg dat este prim sau neprim.
n comparatii
n/2 comparatii
sqrt(n) comparatii
< sqrt(n)/2+1 comparatii
Atentie la verificarea complexitatii asimptotice a testului de primalitate. Nu e trivial 🙂
Problema 4:
Sa se gaseasca pozitia valorii x intr-un tablou de numere.
Numar comparatii?
Best case?
Worst case?
Problema 5:
Sa se gaseasca pozitia valorii x intr-un tablou de numere sortate.
Numar comparatii?
Best case?
Worst case?
Problema 6:
Sa se gaseasca pozitia valorii x intr-un tablou de numere sortate (si uniform distribuite).
Numar comparatii?
Best case?
Worst case?