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



Download 0,81 Mb.
Sana04.04.2022
Hajmi0,81 Mb.
#528329
Bog'liq
Алгоритмларнинг мураккаблигини бахолаш

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


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

РЕЖА:

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) деб ҳисоблаш мумкин.

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


Download 0,81 Mb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish