O‘zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti algoritmlarni loyihalash fanidan Abdullayev Muxammadalining yozgan Mustaqil

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Algoritmlarni loyihalash fanidan

Abdullayev Muxammadalining yozgan

Mustaqil ishi

Mavzu: Eng yomon va o‘rtacha holatlarda algoritmlarni baholashlar

Reja:

1. 
   Kirish
   
2. 
   Asosiy qism
   

1. Eng yomon va o‘rtacha holatlarda algoritmlarni xarakteristkasi

2. Eng yomon va o‘rtacha holatlarda algoritmlarni saralash usullarida tahlili

3. 
   Xulosa
   

Dasturlashda,  berilgan algoritmdan   foydalanish uchun eng yomon va o'rtacha ortacha xolatlarda tekshiriladi. Odatda algoritmni ish vaqti, ya'ni vaqtning murakkabligi korib chiqiladi. Eng yaxshi holat bu n elementlarni kiritish ma'lumotlaridagi minimal qadamlarni bajaradigan funktsiya. Eng yomoni, n o'lchamidagi ma'lumotlarni kiritish uchun maksimal qadamlarni bajaradigan funktsiya. O'rtacha holat - bu elementlarni kiritish ma'lumotlaridagi o'rtacha qadamlarni bajaradigan funktsiya.

Algoritmni tahlil qilishda o'rtacha ko'rsatkich va eng yomon ko'rsatkichlar eng ko'p qo'llaniladi. Bazida eng yaxshi algortimdan ulardan foydalaniladi: masalan, shaxsiy vazifalarning eng yaxshi holatlari ma'lum bo'lgan hollarda, ular umumiy holatlar tahlili aniqligini oshirish uchun ishlatilishi mumkin. Dasturchilar  kutilgan ish vaqtlarini aniqlash uchun ehtimoliy tahlilusullaridan, ayniqsa kutilgan qiymatdan foydalanadilar .

Eng yomon va o‘rtacha holatlarda algoritmlarni xarakteristkasi

Yomon xolatlarni tahlil qilish va o'rtacha xolatlarni samaradorligini tahlil qilish ba'zi o'xshashliklarga ega, ammo amalda odatda turli xil yondashuvlar talab etiladi.

Oddiy kiritish usulini aniqlash juda qiyin va ko'pincha o'rtacha kirish xususiyatlari matematik tavsiflashni qiyinlashtiradigan xususiyatlarga ega .Shunga o'xshab, ma'lum bir "o'rtacha holatlardagi alogritm" ning mantiqiy tavsifi mumkin bo'lsa ham, ular tenglamalarni tahlil qilishda qiyinchiliklarga olib keladi. 

Eng yomon holatlar tahlili xavfsiz tahlilni beradi (eng yomon holat hech qachon etarlicha baholanmaydi), ammo haddan tashqari pessimistikbo'lishi mumkin, chunki bu ko'p bosqichlarni oladigan (real) ma'lumotlar bo'lmasligi mumkin.

Ba'zi holatlarda xavfsizlikni ta'minlash uchun pessimistik tahlildan foydalanish kerak bo'lishi mumkin. Ko'pincha, pessimistik tahlil haddan tashqari pessimistik bo'lishi mumkin, shuning uchun haqiqiy qiymatga yaqinroq bo'lgan, ammo optimistik bo'lishi mumkin bo'lgan (ehtimol ma'lum qobiliyatsiz bo'lish ehtimoli juda kam) amaliy amaliy yondashuv bo'lishi mumkin. O'rtacha va o'rtacha holatlar tahlili o'rtasidagi tafovutni bartaraf etish uchun akademik nazariyadagi zamonaviy yondoshish silliq tahlil deb nomlanadi .

Ko'pincha bajarish uchun oz vaqt talab qiladigan, ammo vaqti-vaqti bilan ko'proq vaqtni talab qiladigan algoritmlarni tahlil qilayotganda (ehtimol cheksiz) qator operatsiyalar davomida eng yomon ish vaqtini aniqlash uchun amortizatsiya qilingan tahlildan foydalanish mumkin . Ushbu amortizatsiya qilingan eng yomon xarajatlar ishning o'rtacha narxiga yaqinroq bo'lishi mumkin, shu bilan birga ish vaqtida kafolatlangan yuqori chegarani ta'minlaydi.

Eng yomon holatlar tahlili eng yomon holatlarning murakkabligi bilan bog'liq 

Eng yomon va o‘rtacha holatlarda algoritmlarni saralash usullarida tahlili

Ko'pincha, algoritmning vaqt murakkabligi kiritish hajmiga bog'liq. Odatda algoritmning vaqt murakkabligi n o'lchamidagi kirish ma'lumotlarini T (n) tartibiga to'g'ri keladi, deyiladi. Amaliyotda T (n) ning aniq qiymatini aniqlash juda qiyin. Shuning uchun ular O-simvolizmidan foydalanib, asimptotik munosabatlarga murojaat qilishadi.

Keyinchalik muhokama qilinadigan algoritmning bajarilish vaqtini nazariy jihatdan hisoblaydigan usul mavjud.

Listing 1.3 - ish vaqtini hisoblash bilan qo'shilgan saralash algoritmining soxta kodi

m hissasini qo'shadi (ammo bu ibora ishlatilgan xotira hajmini hisoblash uchun ishlatilmaydi). Barcha qatorlarning hissalarini qo'shsak, olamizInsertion-Sort protsedurasining umumiy bajarilish vaqtini hisoblash uchun har bir satrda uning narxini (operatsiyalar soni) va ushbu satrning necha marta bajarilishini hisobga olamiz. 2 dan n gacha bo'lgan har bir j uchun (bu erda n = uzunlik [A] - massiv o'lchami), 5 qatori necha marta bajarilishini hisoblash kerak, biz bu raqamni tj bilan belgilaymiz. Davr ichidagi chiziqlar cheklovga qaraganda bir marta kamroq bajariladi, chunki oxirgi tekshirish pastadirdan chiqadi. Bir necha marta takrorlangan m satr bajarilgan operatsiyalar umumiy soniga c

Jarayonning ishlash vaqti nafaqat n ga bog'liq, balki kirishning kirish qismida n o'lchamining qaysi qatori bilan ta'minlanganligiga ham bog'liq. Insertion-Sort protsedurasi uchun massiv allaqachon tartiblangan bo'lsa, eng maqbul holat. Keyin 5-chiziqdagi tsikl birinchi tekshiruvdan so'ng tugaydi (chunki A [i] ≤ tugmachasi i = j - 1), shunda hamma tj 1 ga teng, jami vaqt esa

 

n + b shakli mavjud. Ushbu konstantalar tanlangan qiymatlar bilan belgilanadi c1, ..., c8.Shunday qilib, eng qulay holatda n o'lchovli qatorni saralash uchun zarur bo'lgan vaqt (n), n ning chiziqli funktsiyasi. a va b ba'zi turg'unliklar uchun T (n) = a

Agar qator teskari (pasayish) tartibda joylashgan bo'lsa, ish vaqti

protsedura maksimal bo'ladi: A [j] har bir elementni A [1], ..., A [j - 1] barcha elementlar bilan taqqoslash kerak. Bundan tashqari, tj = j. Chunki

biz eng yomon holatda protsedura vaqti ekanligini tushunamiz

n + s shakliga ega. A, b va c konstantalari bu erda ham c1, ..., c8 qiymatlari bilan aniqlanadi.n2 + bBunday holda, T (n) kvadratik funktsiya, ya'ni. T (n) = a

Odatda algoritmning vaqt murakkabligi n o'lchamidagi ma'lumotlardan T (n) tartibiga to'g'ri keladi, deyiladi. Amaliyotda T (n) ning aniq qiymatini aniqlash juda qiyin. Shuning uchun ular O-simvolizmidan foydalanib, asimptotik munosabatlarga murojaat qilishadi.

Ko'pincha, algoritmning vaqt murakkabligi kiritish hajmiga bog'liq. Odatda algoritmning vaqt murakkabligi n o'lchamidagi kirish ma'lumotlarini T (n) tartibiga to'g'ri keladi, deyiladi. Amaliyotda T (n) ning aniq qiymatini aniqlash juda qiyin. Shuning uchun ular O-simvolizmidan foydalanib, asimptotik munosabatlarga murojaat qilishadi.

Keyinchalik muhokama qilinadigan algoritmning bajarilish vaqtini nazariy jihatdan hisoblaydigan usul mavjud.

Listing 1.3 - ish vaqtini hisoblash bilan qo'shilgan saralash algoritmining soxta kodi