Algoritmlar samaradorligini tahlil qilish

Алгоритмлар самарадорлигини таҳлил қилиш

8-соат
2-мавзу:

1. Таҳлил асослари

Хотира майдонининг мураккаблиги
Алгоритмнинг хотрира майдони мураккаблиги унинг ҳаётий циклида алгоритм талаб қиладиган хотира майдони миқдорини англатади. Алгоритм томонидан талаб қилинадиган хотира майдони қуйидаги иккита компонентнинг йиғиндисига тенг:
1. Муаммо ҳажмидан мустақил бўлган маълум маълумотлар ва ўзгарувчиларни сақлаш учун зарур бўлган хотира майдони. Масалан, ишлатиладиган оддий ўзгарувчилар ва константалар, дастур ҳажми ва бошқалар.
• Ўзгарувчан қисм — ўзгарувчилар томонидан талаб қилинадиган хотира майдони бўлиб, уларнинг ўлчамлари муаммонинг ҳажмига боғлиқ. Масалан, динамик хотирани ажратиш, recursion stack fazo ва бошқалар. 
Har qanday algoritmning S(P) xotira maydoni murakkabligi S(P) = C + SP(I), bu yerda C — o`zgarmas qismi, S(I) esa algoritmning oʻzgaruvchan qismidir, bu I misolning xarakteristikasiga bogʻliq.

Асимптотик белгилар ва асосий самарадорлик синфлари

• Cамарадорликни таҳлил қилиш тизими алгоритм самарадорлигининг асосий кўрсаткичи сифатида алгоритмнинг асосий операциялари сонининг ўсиш тартибига боғлиқ. Ўсишнинг бундай тартибларини солиштириш ва тартиблаш учун учта белгидан фойдаланадилар:
• О (катта о), Ω (катта omega) ва Ө (катта тета)
• t(n) ва g(n) натурал сонлар тўпламида аниқланган ҳар қандай манфий бўлмаган функциялар бўлиши мумкин.
• Бизни қизиқтирган контекстда t(n) алгоритмнинг ишлаш вақти бўлади (одатда унинг асосий операциялар сони C(n) билан кўрсатилади), g(n) эса ҳисоблашни солиштириш учун оддий функция бўлади.

Норасмий равишда O(g(n)) g(n) каби ўсиш тартибидан пастроқ ёки бир хил бўлган барча функциялар тўпламидир.

• Норасмий равишда O(g(n)) g(n) каби ўсиш тартибидан пастроқ ёки бир хил бўлган барча функциялар тўпламидир.
• Шундай қилиб, бир нечта мисолларни келтириш учун қуйидаги тасдиқларнинг барчаси тўғри бўлган функциялар тўплами.

Норасмий кириш