SHPORA.net :: PDA

[ Back ]

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.