Режа: Кириш. Алгоритмларни мураккаблигини аниқлаш

МАВЗУ: АЛГОРИТМЛАРНИНГ МУРАККАБЛИГИНИ БАҲОЛАШ

доцент: М.Х.Худайбердиев

РЕЖА:

1. Кириш.

2. Алгоритмларни мураккаблигини аниқлаш.

3. Мисол.

КИРИШ

Одатда, дастурлаш масалаларини ечишда бир нечта ечим мавжуд бўлади. Улар бир-биридан ишлаш тезлиги, хотирадан қанча жой олиши ёки тушуниш мураккаблиги билан фарқланади. Бунда, асосан, икки хил тушунча мавжуд: алгоритмнинг вақт бўйича мураккаблиги ва хотира бўйича мураккаблиги.

ТАЪРИФ

Алгоритмнинг мураккаблиги - ушбу алгоритмнинг ҳисоблаш жараёнида бошланғич қадамлар сони.

Алгоритмнинг мураккаблигини аниқлаш

Асимптотик таҳлилда олинган мураккаблик функциясини баҳолаш алгоритмнинг мураккаблиги деб аталади. Шуни ёдда тутиш керакки, алгоритмнинг мураккаблиги ҳақида бир нечта маълумот мавжуд. Меҳнатни кўриб чиқиш функциясининг асемпотатикаси - бу фойдаланиш мураккаблиги. Бундан ташқари, сиз қуйидаги қийинчилик турларини белгилашингиз мумкин.

Вақтинча Қийинчилик - узунликдаги кириш маълумотларида алгоритмнинг ишлаш вақтини ассимотик баҳолаш p. Кўриниб турибдики, ҳисоблаш процедураларининг параллеллашуви бўлмаса, алгоритмнинг ишлаш вақти бажарилган операциялар сони бўйича аниқланади. Амалиётларнинг давомийлигини ифода этадиган доимий коэффициентлар вақтинча мураккаблик тартибига таъсир қилмайди, шунинг учун амалдаги ва вақтинчалик қийинчиликлар формулалари кўпинча бир-бирига мос келади.

Сиғим Мураккаблик - бу вақтнинг ўзида мавжуд бўлган маълумотларни узатишда алгоритмни бажаришда бир вақтнинг ўзида мавжуд бўлган шкалалар сонини ассимотик жиҳатдан баҳолаган p.

Сиғим Мураккаблик - бу вақтнинг ўзида мавжуд бўлган маълумотларни узатишда алгоритмни бажаришда бир вақтнинг ўзида мавжуд бўлган шкалалар сонини ассимотик жиҳатдан баҳолаган p.

Такрорий Мажбурият - бу алгоритмдаги бошқарув тузилмалари сонининг ва уларнинг талқиннинг ўзига хос хусусиятларига хосдир.

Когнитив Мажбурият - амалий ҳудудлар мутахассисларини тушуниш учун алгоритмнинг мавжудлиги хусусиятидир.

Algoritmning vaqt bo'yicha murakkabligi - bu uning ishlash vaqtini unga kiruvchi (input) ma'lumot(lar)ga nisbatan o'zgarishiga aytiladi.

Algoritmning vaqt bo'yicha murakkabligi - bu uning ishlash vaqtini unga kiruvchi (input) ma'lumot(lar)ga nisbatan o'zgarishiga aytiladi.

Algoritmning xotira bo'yicha murakkabligi - huddi yuqoridagi kabi, algoritm ishlashi uchun unga kerak bo'lgan xotira hajmini (operativ xotiradan olinadigan joy) kiruvchi (input) ma'lumot(lar)ga nisbatan o'zgarishiga aytiladi.

Дастурий масалалар ечишда юқоридаги 2 та омил энг муҳимлари саналади. Шунинг учун сизнинг ечимингиз қандай ҳолатларда ўртача қанча вақт ишлаши ва оператив хотирадан қанча жой эгаллашини билиш муҳим ҳисобланади.

Дастурий масалалар ечишда юқоридаги 2 та омил энг муҳимлари саналади. Шунинг учун сизнинг ечимингиз қандай ҳолатларда ўртача қанча вақт ишлаши ва оператив хотирадан қанча жой эгаллашини билиш муҳим ҳисобланади.

Дастурлаш мусобақаларида, асосан, биринчи жиҳатга кўпроқ эътибор қаратилади. Лекин аниқ вақт, жудаям кўп омилларга боғлиқ: компьютер қурилмалари, процессори, операцион тизим ва ҳоказоларга. Шунинг учун ҳам бизга фақат унинг назарий жиҳатдан ишлаш вақтини баҳолаш муҳимдир.

Мисол

Бунда ҳар бир амал ўзгармас c вақт сарфлайди деб ҳисоблайлик. Биз алгоритм мураккаблигини ҳисоблаганда энг ёмон ҳолатни ҳисобга олишимиз керак. Бу ҳолатда эса х элемент массивда ёъқ ҳолат энг ёмон ҳолат ҳисобланади, яъни массивнинг барча N та элементи кўриб чиқилиши керак. Умумий ҳолатда, алгоритм ишлаши учун N*c + c (N та if учун ва битта return учун). Алгоритм мураккиблигини баҳолаганда константалар эътиборга олинмайди ва бу юқоридаги алгоритм мураккаблигини О(N) деб ҳисоблаш мумкин.

Бунда ҳар бир амал ўзгармас c вақт сарфлайди деб ҳисоблайлик. Биз алгоритм мураккаблигини ҳисоблаганда энг ёмон ҳолатни ҳисобга олишимиз керак. Бу ҳолатда эса х элемент массивда ёъқ ҳолат энг ёмон ҳолат ҳисобланади, яъни массивнинг барча N та элементи кўриб чиқилиши керак. Умумий ҳолатда, алгоритм ишлаши учун N*c + c (N та if учун ва битта return учун). Алгоритм мураккиблигини баҳолаганда константалар эътиборга олинмайди ва бу юқоридаги алгоритм мураккаблигини О(N) деб ҳисоблаш мумкин.

ЭЪТИБОРИНГИЗ УЧУН РАХМАТ