Muhammad al-Xorazmiy nomidagi tatu qarshi filiali tt va kt fakulteti ax 12 20 guruh talabasi Shodmonov Javohirbeknining Algoritmlarni loyihalash fanidan

Muhammad al-Xorazmiy nomidagi TATU
Qarshi filiali TT va KT fakulteti
AX_12_20 guruh talabasi Shodmonov Javohirbeknining Algoritmlarni loyihalash fanidan


1-Mustaqil ishi

Mavzu: Algoritm murakkabligining statik va dinamik o’lchovlari

Bajardi: J . Shodmonov
Qabul qildi: A. Ravshanov
Reja :

1. 
   Vaqt va xotira hajmi bo’yicha qiyinchiliklar ;
   
2. 
   Algoritmlarni eng yomon va o’rtacha holatlarda baholash ;
   
3. 
   Algaritmlarni vaqt va hajmiy murakkabligini baholashda tekis va logorifmik solishtirma mezonlari ;
   

1. Biz asosan algoritmlarning vaqt bo'yicha murakkabligini muhokama qilamiz, ammo ish bajarish uchun u yoki bu algoritmga qancha xotira kerakligi haqida ham aytish mumkin. Kompyuter xotirasi (ham ichki, ham tashqi) hajmi chegaralangan. Kompyuterlar rivojlanishining dastlabki bosqichlarida bu tahlil uslubiy xarakterga ega edi. Barcha algoritmlar chegaralangan xotira yetarli yoki qo‘shimcha maydonni talab qiluvchi algorilmlarga bo’linadi. Ko‘pincha dasturlovchilar xotirasiga ega va tashqi qurilmalar talab qilmaydigan sekin ishlovchi algoritmni tanlashar edi. Kompyuter xotirasiga bo‘lgan talab juda katta edi, shuning uchun qaysi ma’lumotlar saqlanib qoladi, bunday saqlashning samarali usullari qanday kabi savollar o‘rganilar edi. Faraz qilaylik, masalan, biz -10 dan +10 gacha intervaldagi verguldan keyin bitta o‘nli belgiga ega bo‘lgan moddiy son yozyapmiz. Moddiy sonni yozishda ko'pchilik kompyuterlar 4 dan 8 baytgacha xotira sarflaydi, lekin agar bu sonni avvaldan 10 ga ko‘paytirsak, -100 dan + 100 gacha intervaldagi butun son hosil qilamiz va uni saqlash uchun bor yo'g‘i bir bayt sarflanadi. Birinchi variant bilan solishtirsak, 3-7 bayt tejashga erishildi. 1000 ta shunday son saqlaydigan dastur 3000 dan 7000 baytgacha tejaydi. Agar o‘tgan asming 80 yillarida kompyuterlarning xotirasi 65536 bayt bo‘lganligini e'tiborga olsak, jiddiy tejash ko'zga tashlanadi. Aynan shu kompyuter dasturlarining uzoq yil ishlashi xotirani tejash zaruriyati bilan bir qatorda 2000 yil muammo tug‘dirdi. Agar sizning dasturingiz turli sanalardan foydalansa, yilni yozish uchun 1999 o‘miga 99 ifodasini saqlagan holda joyning yarmini tejasa bo‘ladi. 80-yillardagi dastur mualliflari mahsulotlari 2000-yilgacha yashashini taxmin ham qilishmagan edi. Hozirgi kunda bozorlarda taklif qilinayotgan dasturiy ta’minotga nazar tashlasak, xotiraning bunday tahlili o'tkazilmaganligi ayon bo‘ladi. Oddiy dasturlar uchun zarur xotira hajmi megabaytlarda o‘lchanadi. Dastur tuzuvchilar joyni tejash ehtiyojini his qilmayotganga o‘xshaydilar, ularning fikricha, agar foydalanuvchida yetarli xotira bo'lmasa, u dastur bajarilishi uchun yetmayotgan 32 yoki undan ortiq megabayt xotira yoki uni saqlash uchun yangi qattiq disk sotib oladi. Natijada kompyuterlar o ‘zining belgilangan muddatidan avval yaroqsiz holga kelib qoladi. Yaqinda tarqalgan cho‘ntak kompyuterlari (PDA – personal digital assistant) yangi ohang olib kirdi Bunday qurilmaning xotirasi ham m a’lumotlar, ham dasturlar uchun 2 dan 8 megabaytgacha. Shuning uchun ham m a’lumotlami ixcham saqlashni ta’minlovchi kichik dasturlarni yaratish qiyin bo‘lib qolmoqda.

2. Algoritm murakkabligini baholash. Xotira yoki vaqt. Mavjud algoritmlarning ko’pchilig xotira va tezlik o’rtasida tanlovni taklif qiladi. Masala tez ishlashi va katta xotira egallashi yoki sekin ishlashi va kichik xotira hajmini egallashi mumkin. Bu holatda eng odatiy misollardan biri eng qisqa masofani topish masalasi bo’la oladi. Bunda siz o’zaro bog’liq bo’lgan shahar orasidagi istalgan ikki nuqta orasidagi eng qisqa masofani topishingiz kerak bo’ladi. Bunda biz barcha nuqtalar orasidagi qisqa masofalarni aniqlab ularni jadval shaklida saqlab qo’yishimiz mumkin. Va biz eng qisqa masofani aniqlashimizga to’g’ri kelganda shunchaki jadvaldan a’lumotni olib qo’yishimiz mumkin bo’ladi. Natijani shu zahoti olishimiz mumkin, ammo bu juda katta hajm talab qiladi. Masalan biror katta xaritada 10 minglab nuqtalar bo’lishi mumkin va bizning jadvalimiz buning uchun10 milliarddan ortiq ma’lumotni saqlashiga to’g’ri keladi va bu taxminan 10GB ga yaqin xotirani band etishi mumkin. Ushbu holatdan hajm-vaqt murakkabligi kelib chiqadi. Shunda algoritm vaqt bo’yicha ishlash tezligi yoki hajm bo’yicha ishlash tezligi bilan baholanadi. Biz asosiy e’tiborni vaqt bo’yicha urakkablikka qaratamiz lekin shu bilan birga foydalaniladigan xotira hajmini ham aniq belgilashimizga to’g’ri keladi. Ketma-ketlikni baholash. Biz algoritmlarni o’zaro baholashimizda ularga kiruvchi ma’lumotni ham e’tiborga olishimizga to’g’ri keladi. Chunki ayni bir saralash algoritmi uchun 1000 ta kiruvchi elementni saralash 1s, 100 000 element uchun esa 4-5 soniya ketadigan bo’lsa, boshqa bir algoritm uchun esa bor-yo’g’i 2 s ketishi mumkin. Bunday sharoitda qaysi algoritm yaxshi ekanini aytish mushkuldir. Umumiy holatda esa algoritmni murakkabligini ayni bir kattalik bilan baholash mumkin bo’ladi. Buni quyidagicha tushunish mumkin: agar algoritmga kiruvchi N ma’lumotlar oshganida algoritmning bajarilish vaqti f(N) funksiya bilan bir xilda ortsa algoritm O(f(N)) murakkablikka ega deyiladi. Keling, yaxshisi A[NxN] matritsaning har bir qatoridagi maksimal elementni topishni ko’rib chiqamiz: Ushbu algoritmda i o’zgaruvchi 0 dan N-1 gacha o’zgarib kelyapti hamda uning har bir o’zgarishida j o’zgaruvchi ham shu oraliqda o’zgaryapti.

Demak bunda jami N*N marta takrorlanish sodir bo’lyapti. Bundan esa f(N) = N*N ga teng bo’ladi va algoritmning murakkabligi O(N*N) ekanligini aniqlashimiz mumkin. Endi algoritmni murakkablik darajasini baholashni ko’rib chiqaylik. Bunda algoritmdagi eng tez o’suvchi qismdan foydalanish kerak bo’ladi. Tasavvur qiling algoritm N^3 + N urakkablikka ega bo’lsin. Bunda biz murakkablikni O(N^3) deb olishimiz yetarli bo’ladi. Chunki bu yerda tez o’suvchi qism bu N^3. Ya’ni +N ta qo’shimcha amalni hisoblashning hojati qolmaydi. Misol uchun N=100 bo’lsin, shunda jami 1000100 ta amal bajariladi va bu N^3 dan atigi 0.01% gagina farq qiladi.

Murakkablikni baholash. Dasturdagi murakkab algoritmlar asosan funksiya va protseduralarda bo’ladi. Keling, buni ko’rish uchun Fast hamda Slow nomli funksiyalar yaratib olaylik va bu funksiyalarning turli xil ko’rinishdagi murakkabligini baholab ko’raylik. Demak ushbu kodni ko’rib chiqamiz.Slow funksiyasi O(N^3) murakkablikka ega bo’lib unda ichma ich 3 ta for sikli mavjud: N*N*N. Buni osonlik bilan ko’rish mumkin. Endi Fast funksiyasini ko’radigan bo’lsak unda ichma-ich 2 ta for sikli mavjud. Ammo ikkinchi siklda biz Slow funksiyasini chaqirganmiz. Bu esa algoritmning murakkabligini yanada oshiradi, ya’ni O(N^2) * O(N^3) = O(N^5). Both funksiyasida biz ikkala funksiyadan ham foydalandik. Bunda funksiyalar ketma-ket qo’llangani sabab ular ichidan murakkabligi katta bo’lgan funksiya asosiy funksiyaning murakkabligi bo’ladi ya’ni O(N^2) + O(N^5) = O(N^5). Endi berilgan N=100 da algoritmning ishlash vaqtini ko’radigan bo’lsak u quyidagicha:
Demak bu Both funksiyasi 570 soniyadan ko’proq vaqt ishladi. Boshqa xarakteristikadagi mashinada bu ko’p yoki kam bo’lishi mumkin. Xulosa qiladigan bo’lsak oddiy takrorlanish algoritmlarining murakkabligi undagi takrorlanishlarning soniga bog’liq bo’ladi va buni aniqlash ancha oson.
Rekursiv algoritmlarni baholash
Oddiy rekursiya. Rekursiv funksiyalar bu o’z-o’zini chaqiruvchi funksiyalardir. Rekursiv algoritmlarni baholash juda murakkabdir. Ularning murakkabligini baholash nafaqat ichki foydalanilgan funksiyalar, yana rekursiyaning takrorlanishiga ham bog’liq bo’ladi. Keling oddiy rekursiya misolida faktorialni hisoblash funksiyasini ko’raylik:
Ushbu rekursiv funksiyada ortiqcha sikllar va ortiqcha funksiyalar mavjud emas shuning uchun bu funksiya faqat N marta takrorlanadi va uning murakkabligi O(N) ga teng bo’ladi. Ushbu dasturning ishlash vaqti quyidagicha. Bundan tashqari rekursiv funksiyalarda rekursiya chuqurligi ya’ni rekursiyaning qancha marotaba takrorlanishi muammosi mavjuddir. Bu esa mashinaning xotira bilan bog’liq muammolariga bog’liqdir.


Xulosa :
Xulosa o’rnida aytadigan bo’lsak, algoritmlar asosan quyidagicha ko’rinishdagi murakkabliklarda bo’ladi va barcha algoritmlarni baholashimiz uchun mana shu murakkabliklar yetarli bo’ladi