Algortim murakkabligini baholash usullari Vaqt bo’yicha murakkabligini baholash



Download 118,69 Kb.
bet1/2
Sana13.07.2021
Hajmi118,69 Kb.
#118112
  1   2
Bog'liq
alg murakkabligini baholash


Reja:

  1. Algortim murakkabligini baholash usullari

  2. Vaqt bo’yicha murakkabligini baholash

  3. Misollarni solishtirish

Ma’ruza bayoni

Bu darsimizda sizlar bilan algoritm murakkabligini qanday baholash va bu narsa nima uchun muhimligi haqida to'xtalib o'tamiz. Hamda O-notatsiysa (O(n), O(n^2)) nimani anglatishini ko'rib o'tamiz.

Odatda, dasturlash masalalarini yechishda bir nechta yechim mavjud bo'ladi. Ular bir-biridan ishlash tezligi, xotiradan qancha joy olishi yoki tushunish murakkabligi bilan farqlanadi. Bunda, asosan, ikki xil tushuncha mavjud: algoritmning vaqt bo'yicha murakkabligi va xotira bo'yicha murakkabligi.

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.

Dasturiy masalalar yechishda yuqoridagi ikkita omil eng muhimlari sanaladi. Shuning uchun sizning yechimingiz qanday holatdlarda o'rtacha qancha vaqt ishlashi va operativ xotiradan qancha joy egallashini bilish muhim hisoblanadi.

Dasturlash musobaqalarida, asosan, birinchi jihatga ko'proq e'tibor qaratiladi. Lekin aniq vaqt, judayam ko'p omillarga bog'liq: kompyuter qurilmalari, protsessori, operatsion tizim va hokazolarga. Shuning uchun ham bizga faqat uning nazariy jihatdan ishlash vaqtini baholash qiziq. Bunda O() (O - notatsiya)dan foydalaniladi.

O notatsiya ta'rifiga o'tishdan oldin bitta misol keltirib o'tamiz:

N ta elementli massivdan x elementni qidirish kerak bo'lsin. Oddiy yechim, chiziqli qidiruvni ko'ramiz, ya'ni massiv har bir elementni berilgan elementga birma-bir solishtirib ko'ramiz.

for i : 1 to length of A

if A[i] is equal to x

return TRUE

return FALSE

Bunda har bir amal o'zgarmas c vaqt sarflaydi deb hisoblaylik. Biz algoritm murakkabligini hisoblaganda eng yomon holatni hisobga olishimiz kerak. Bu holatda esa x element massivda yo'q holat eng yomon holat hisoblanadi, ya'ni massivning barcha N ta elementi ko'rib chiqilishi kerak. Umumiy holatda, algoritm ishlashi uchun N*c + c (N ta if uchun va bitta return uchun). Algoritm murakkibligini baholaganda konstantalar e'tiborga olinmaydi va bu yuqoridagi algoritm murakkabligini O(N) deb hisoblash mumkin.

Ya'ni kiruvchi massiv hajmi oshib borgan sari algoritmimiz ishlash vaqti ham N ga bog'liq oshib boradi (bu holatda chiziqli nisbatda). Endi ta'riflarga o'tadigan bo'lsak:

O-notatsiya



Ta’rif: Agar shunday konstanta soni mavjud bo’lsaki, bunda barcha natural n sonlari uchun f(n)≤c*g(n) shart bajarilsafunksiya funksiyadan tez o’smaydi va f(n)≤O(g(n)) ko’rinishida yoziladi.

O-notatsiya yuqori chegarani, ya'ni eng yomon holatni baholash uchun ishlatiladi. Shu sababdan ham dasturlash masalalarini yechishda O-notatsiyadan eng keng foydalaniladi.

Ω-notatsiya (Omega notatsiya)

Ta'rif: Agar shunday konstanta soni mavjud bo’lsaki, bunda barcha natural n sonlari uchun f(n)≥c*g(n) shart bajarilsa, g funksiya f funksiyadan tez o'smaydi va f(n)≥Ω(g(n)) ko’rinishida yoziladi.

Ω-notatsiya pastki chegarani ifodalashda ishlatiladi.

Θ-notatsiya (Teta notatsiya)

Ta'rif: Agar shunday konstanta soni mavjud bo’lsaki, bunda barcha natural n sonlari uchun f(n)=c*g(n) shart bajarilsa, f funksiya g funksiya bilan bir xilda o'sadi va f(n)=Θ(g(n)) ko’rinishida yoziladi.

Yanayam soddaroq tushunish uchun quyidagi jadvalni keltiramiz



Bu safar ham shu mavzumizni davom ettirib, algoritm murakkabligini baholashdagi asosiy qoidalar va algoritmik masalalarni yechishda eng ko'p uchraydigan algoritmik assimptotikalarga to'xtalib o'tamiz. (O(n*logn), O(n)) kabi.

Demak, birinchi navbatda algoritm murakkabligini baholashdagi asosiy qoidalar:

  1   2




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