Norqulova dilfuzaning algoritimlarni loyhalash

  
MA’VZU:-4;5.Algoritimlarni vaqt va hajmiy 
murakkabligini 
baholashda tekis va logorifmik solishtirma mezonlari. 
Reja:
Samaradorlik ko’rsatkichlari.
Algoritmlarni murakkabligini aniqlash.
Hisoblash qobiliyati
Algoritmlarni tahlil qilishning asosiy vazifasi kirish ma'lumotlari hajmining 
oshib borishi bilan resurslarga bo'lgan talabni (vaqt va xotira xarajatlari) 
o'lchash usullarini aniqlashdir. Shundan so'ng, o'sish sur'ati qonuniyatlarini 
tavsiflash uchun zarur bo'lgan matematik mexanizm ishlab chiqiladi. Kirish 
ma'lumotlari hajmini oshirish bilan turli xil funktsiyalar; "bitta funktsiya 
boshqasiga qaraganda tezroq o'sadi" iborasi nimani anglatishini aniqlab 
olishga yordam beradi. Ba'zi hollarda, yaxshi bajarilish vaqtiga erishish 
yanada murakkab ma'lumotlar tuzilmalaridan foydalanishga bog'liq va 
bo'lim oxirida biz bunday ma'lumotlar strukturasining juda foydali misolini 
ko'rib chiqamiz: ustuvor navbatlar va ularni uyum(kucha, heap) asosida 
amalga oshirish.
Asosiy maqsad - hisoblash muammolarining samarali algoritmlarini izlash. 
Ushbu umumiylik darajasida kompyuterni hisoblashning butun sohasi ushbu 
mavzu bilan bog'liq bo'lib tuyuladi; bizning yondashuvimiz boshqalardan 
qanday farq qiladi? Algoritmlarni ishlab chiqishda umumiy mavzular va 
loyihalash tamoyillarini aniqlashga harakat qilamiz. Bizni samarali 
algoritmlarni loyihalashning asosiy usullarini minimal ma'lumot bilan 
namoyish etuvchi paradigmatik masalalar va usullar qiziqtiradi.
Algoritmni bajarilish qadami - bu ijrochi tomonidan bitta ko‘rsatmaning 
bajarilishidir. Bir masalani hal etuvchi ikkita algoritmdan kam qadam talab 
qilinayotgani samaraliroqdir. Samaradorlik o‘lchovi - bu bor-yo‘g‘i 
qadamlar sonidir. Lekin chuqurroq e’tibor berib qarasak, bu ta’rifdagi 
mujmal tomonlarni aniqlaymiz. Ba’zan avval uchragan algoritmlardagidan 
ko‘ra vaziyat murakkabroq bo’ladi.

---

Algoritmlar murakkabligi bilan ham farqlanishi mumkin. Algoritmning 
murakkabligini uning matnidagi satrlar soni bilan o‘lchaymiz. Shu bilan 
birga quyidagi ikki satrni bir tuzilmaning ikki qismi bo‘lgani uchun bittaga 
hisoblaymiz
TAKRORLANSIN  MARTA TAMOM
Mana, masalan, quyidagi algoritmda:
1 ni qo‘sh
TAKRORLANSIN 6 MARTA 2 ga ko‘paytir
1 ni qo‘sh 
TAMOM
1 ni qo‘sh 
TAKRORLANSIN 6 MARTA  TAMOM
2 ga ko‘paytir 1 ni qo‘sh faqat 4 ta satr bor. Bu uning murakkabligi 4 
ekanligini bildiradi.
Shuni aytib o‘tish joizki, hozir biz ko’rgan algoritm murakkabligi va 
samaradorligi o‘zaro tengdir. Masalan, bo‘ri, echki va karamni daryodan 
o‘tkazish algoritmi ham 7 satrdan iborat ham u 7 qadamda bajariladi.
Bu yerda bizni kerakli vositamiz bor: bu TAKRORLANSIN - MARTA 
tuzilmasi. Shuning uchun oshiruvchi tomonidan 17 sonini hosil qilish 
algoritmi 3 satrdan iborat bo‘ladi (eslatma: tuzilma 1 ta satr deb hisoblanadi):
1 ni qo‘sh
TAKRORLANSIN 16 MARTA
1 ni qo‘sh
TAMOM
Endi bu algoritmning samaradorligi 17 ga, murakkabligi esa 17 emas, 3 ga 
teng. Askarlar va qayiq masalasi algoritmida 60 ta askarni daryodan 
o‘tkazish uchun 240 qadam bajariladi, algoritm matni esa 5 satrdan iborat. 
Bu algoritmning samaradorligi 240 ga, murakkabligi esa 5 ga teng. Baqa 
uchun tuzilgan “Baqa toq sondagi n ta bargli nilufarning 1 tartib raqamli 
bargiga tushdi. U barcha pashshalarni yeb 2 tartib raqamli barg ustiga borish 
algoritmini tuzing.” masalani algoritmida qadamlar sonini hisoblaymiz: son 
+ 1 + son — 1 = (n —1):2 + (n — 1):2 = n — 1.
Demak, har qanday n toq son uchun algoritmni samaradorligi n - 1 ga teng 
ekan. Algoritmning murakkabligi esa n toq son nechaga teng bo‘lishidan 
qat’iy nazar, 5 ga teng bo‘ladi!

---

Xulosa. Baqa masalasiga oid algoritmlarning samaradorligi faqat n sonining 
qiymatiga bog‘liq. Chunki masala shartida Baqa har bir bargdagi pashshani 
yeb chiqishi talab qilinadi. U holda barglar soni n ta ekanligi va Baqa biror 
bargning ustida turgandan keyin harakat boshlanganligidan qadamlar soni 
doimo n-1 ta bo‘lishi kelib chiqadi.
Haqiqatan, masalan, agar 1 tartib raqamli bargdan 4 tartib raqamlibargga 
o‘tish кегак bo‘lsa, u holda barcha imkoniyatlarni 1.1—1.2-rasmlarda, agar 
1 tartib raqamli bargdan 5 tartib raqamli bargga o‘tish kerak bo‘lsa, u holda 
barcha imkoniyatlarni 1.3—1.5-rasmlardan ko‘rishimiz mumkin.
1.1-rasm
1.2-rasm
1.3-rasm

---

1.4-rasm
1.5-rasm
Va nihoyat, yana bir izoh. Samaradorlik va murakkablik talabi ko‘pincha 
birbiri bilan ziddiyatga kirishadi. Bu mutlaqo tabiiy. Axir, mashina sotib 
olayotgan bo‘lsangiz, eng chiroyli va qulay mashinaning eng arzon 
bo‘Iishiga umid qilmaysiz. Algoritmlashda ham shunday. Agar sizga juda 
samarador algoritm kerak bo‘lsa, bu algoritm boshqalariga nisbatan ancha 
murakkabroq bo’lishi ehtimoli katta. Amaliyotda esa oqilona murosaga 
kelishga to ‘g‘ri keladi.
 
Hisoblash qobiliyati. Ko'plab muammolarda uchraydigan yana bir xususiyat 
- bu ularning asosan diskretligi. Ko'plab muammolarda uchraydigan yana bir 
xususiyat-bu ularning asosiy ajralib turishi. Boshqacha qilib aytganda, bu 
shunday masalalarki, ularda yechim kombinatorial variantlarning keng 
to'plamidan qidirib topiladi; maqsad aniq belgilangan shartlarni 
qanoatlantiradigan echimni samarali topishdir.
Hisoblash samaradorligi tushunchasini aniqlash uchun, biz birinchi navbatda 
ish vaqtining samaradorligiga e'tibor qaratamiz: algoritmlar tez ishlashi 

---

kerak. Ammo algoritmlar boshqa resursrlardan foydalanish nuqtai nazaridan 
ham samarali bo'lishi mumkinligini tushunish muhimdir. Xususan, 
algoritm tomonidan ishlatilinadigan xotira miqdori ham samaradorlikning 
muhim jixati bo'lishi mumkin.
Algoritm samaradorligi. (1)T: algoritm samarali deb ataladi agar real kirish 
ma'lumotlari uchun u tezkor amalga oshirilsa.
(2)T: algoritm samarali deb ataladi agar u sifatli bajarilishni “to’liq 
qidirish”(полнiy перебор)ga nisbatan tezroq ta'minlasa.
"To'liq qidirish" usuliga qaraganda ancha yaxshi ishlashni ta'minlaydigan 
algoritmlar, deyarli har doim qimmatli evristik g'oyani o'z ichiga oladi, 
buning natijasida ushbu yaxshilanishga erishiladi; Bundan tashqari, ular 
ko'rib chiqilayotgan masalaning ichki tuzilishi va hisoblash qobiliyati haqida 
foydali ma'lumotlarni taqdim etadilar.
Polinomial vaqt samaradorlik ko'rsatkichi sifatida. Tabiiy kombinatorial 
masalalarda qidirish vaqti, kirish ma'lumotlari N hajmiga nisbatan 
eksponensional o'sishga moyildir; agar o'lcham bittaga ko'paysa, unda 
imkoniyatlar xajmi bir necha marta ko'payadi. Bunday masalalarni yechish 
uchun yaxshi algoritm yanada samarali miqyoslash modeliga ega bo'lishi 
kerak; kirish ma'lumotlarining kattalashib borishi bilan o’zgarmas 
ko’paytuvchiga(aytaylik, ikki baravar) oshishi bilan algoritmning bajarilish 
vaqti ham qandaydir o’zgarmas S ko’paytuvchiga ko'payishi kerak.
(3)T: Agar algoritm polinomial bajarilish vaqtiga ega bo'lsa, u samarali deb 
ataladi.
Lekin, polinomial vaqt d ning katta qiymatlarida yaxshi natija bermasligi 
mumkin, masalan d>=100 holatda bu son juda katta bo’ladi, natijada 
polinomial bajarilish vaqti kattalashib ketadi. Algoritm ishlayveradi. Bu 
xolda N^d faqat chegara vazifasini o’taydi.
Xulosa. Ushbu mustaqil ishni bajarish davomida 
algoritmlarni 
samaradorligini 
va 
murakkabligini 
baholash 
to’g’risida ko’plab 
ma’lumotlarga ega bo’lindi. Turli masalalar orqali alagoritmlarni