Algoritmi omadused. Algoritmide asümptootiline analüüs
a) Algoritmi iseloomustamiseks kasutatakse järgmisi mõisteid:
* Korrektsus (algoritm lahendab "õiget" ülesannet, tulemus vastab spetsifikatsioonile).
* Määratletus (sammud on lõplikud ja üheselt määratud).
* Kirjelduse lõplikkus (algoritm on kirjeldatav lõpliku arvu sammudega).
* Peatuvus. Töö lõpetamine mistahes sisendi korral - kõikjal määratud algoritm. Osaline e. "poollahenduv" algoritm kas annab tulemuse või ei lõpeta tööd.
* Determinism (samade algandmete korral vastus sama, lahenduskäik on korratav) vs. mittedeterminism (näit. "tõeline" juhuarvude generaator).
* Universaalsus (lahendab probleemide klassi: sisend -> väljund ).
* Keerukus (efektiivsus, kas lõpetamise aeg ja/või mälumaht on praktilised).
b) Asümptootilised hinnangud, "suure O", "väikese o", "suure oomega", "väikese oomega" ja teeta-tähistused:
"f kasvab mitte kiiremini kui g" ( f big-Oh g ) - leiduvad konstant c>0 ja koht N nii, et iga n>N korral
|f(n)| < c|g(n)|
f ja g suhe on ülalt tõkestatud.
"f kasvab aeglasemalt kui g" ( f little-oh g ) - mistahes konstandi c>0 jaoks leidub koht N nii, et iga n>N korral
|f(n)| < c|g(n)|
f ja g suhe pole alt tõkestatud.
"f kasvab niisama kiiresti kui g" ( f big-Theta g ) - leiduvad konstandid b, c>0 ja koht N nii, et iga n>N korral
b|g(n)| < |f(n)| < c|g(n)|
f ja g suhe on nii ülalt kui ka alt tõkestatud.
"f kasvab mitte aeglasemalt kui g" ( f big-Omega g ) - "g kasvab mitte kiiremini kui f"
f ja g suhe on alt tõkestatud.
"f kasvab kiiremini kui g" ( f little-omega g ) - "g kasvab aeglasemalt kui f"
f ja g suhe pole ülalt tõkestatud.