шпаргалка

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.





КАТЕГОРИИ:

Network | английский | архитектура эвм | астрономия | аудит | биология | вычислительная математика | география | Гражданское право | демография | дискретная математика | законодательство | история | квантовая физика | компиляторы | КСЕ - Концепция современного естествознания | культурология | линейная алгебра | литература | математическая статистика | математический анализ | Международный стандарт финансовой отчетности МСФО | менеджмент | метрология | механика | немецкий | неорганическая химия | ОБЖ | общая физика | операционные системы | оптимизация в сапр | органическая химия | педагогика | политология | правоведение | прочие дисциплины | психология (методы) | радиоэлектроника | религия | русский | сертификация | сопромат | социология | теория вероятностей | управление в технических системах | физкультура | философия | фотография | французский | школьная математика | экология | экономика | экономика (словарь) | язык Assembler | язык Basic, VB | язык Pascal | язык Си, Си++ |