TANLOV BO’YICHA SARALASH. ALGORITMNING MURAKKABLIGINI TAHLIL QILISH Mundarija Kirish .................................................................................................................................................................. 2 1. Algoritmlarning asimptotik tahlili ................................................................................................................... 3 2. Saralash algoritmlari ....................................................................................................................................... 6 3. Ustuvor navbatlarni piramidada qurish .......................................................................................................... 7 4. TOPSHIRIQ .................................................................................................................................................... 13 5. Asimptotik Tahlil ........................................................................................................................................... 23 Xulosa .............................................................................................................................................................. 27 Adabiyotlar ro’yhati: ........................................................................................................................................ 28

Kirish Qandaydir masalani hal etishga kirishishdan avval buning uchun eng yaxshi uslub izlanadi va uni qay tarzda tavsiflash aniqlanadi. Boshqacha qilib aytganda, biz doimo maqsadi ba’zi bir zaruriy natijaga erishishdan iborat, amallar ketma- ketligi bilan berilgan turli-tuman qoidalarga duch kelamiz. Bunday amallarning ketma-ketligi algoritm deb ataymiz. Matematikada algoritmning murakkabligi, xal etish masalalari va ularni ishlab chiqish prinsiplarini o‘rganadigan maxsus “Algoritmlarni tahlil qilish” bo‘limini o’rganib chiqamiz. Algoritmlar nazariyasi – algoritmlarning umumiy xossalari, qonuniyatlari va ularni tasvirlanishining turli-tuman formal modellarini o‘rganish bilan shug'ullanadi. Algoritm tushunchasini formallashtirish asosida ularning samaradorligi taqqoslash, ularning ekvivalentligi tekshirish, qo‘llanilish sohasini aniqlash mumkin. Ushbu kurs ishlarida mo’ljallangan barcha misollar, algoritmlar va ularning C++ dasturlash muhitidagi kodlari bilan keng yoritib berilgan. Har bir masalada ishdan maqsad, qisqacha nazariy qism, algoritmik tahlili keltirilgan. Dasturlarni yaratish jarayonida qo’yilgan masalaning yechish algoritmi dastlab to’g’ri ishlab chiqilishi muhim ahamiyatga ega. Shuning uchun algoritmlarni tuzish va dasturlarni ishlab chiqish bir-biri bilan chambarchas bog’liq jarayonlardir. Algoritm tushunchasi zamonaviy matematika va informatikaning asosiy tushunchalaridan biri hisoblanadi. Algoritm termini o’rta asrlar ulug’ matematigi al-Xorazmiy nomidan kelib chiqqan. XX asrning 30-yiligacha algoritm tushunchasi ko’proq matematik ma’no emas, balki metodologik ma’noni kasb etar edi. Algoritm deganda, u yoki bu masalalar sinfini yechish imkonini beruvchi aniq ifodalangan chekli qoidalar majmui tushunilgan.Hozirda ham ixtiyoriy masalani yechish uchun ma’lum qonun qoidalar sifatida fanda qo’llanilib kelinmoqda. 2

1. Algoritmlarning asimptotik tahlili Masalani yechish ko’pchilik hollarda ishlash prinspidan kelib chiqqan holda bir nechta algoritmlardan bittasini tanlashga to’g’ri keladi. Belgilangan qadamlardan keyin turli kiritiluvchi ma’lumotlarda ularning bari masalaning to’g’ri yechimiga olib boradi. Shunday bo’lsada mavjud variantlardan optimal metodni tanlashimiz lozim. Optimallikning kriteriyasi bu algoritmning murakkabligidir. Odatda ikkita vaqt va hajm (egallangan joy) bo’yicha murakkablikka ajratishadi. Vaqt bo’yicha murakkablik berilgan masalani yechishda algoritm tomonidan amalga oshiriladigan elementar amal(instruksiya)larning soni bilan belgilanadi. Hajm bo’yicha murakkablik algoritm tomonidan foydalanilgan hotira hajmi bilan o’lchanadi. Endilikda biz faqat vaqt bo’yicha murakkablikni ko’rib chiqamiz. Algoritmlarning ikki xil turi ajratib ko’rsatiladi, bular: takrorlanuvchi algoritmlar va rekursiv algoritmlar. Takrorlanuvchi algoritmlar asosida sikl va shart operatorlari yotadi. Bu sinf algoritmlarining analizi barcha sikllar va ular ichidagi amallar hisobini taqazo etadi. Rekursiv algoritmlar (rekursiv funksiya – o’z-o’zini chqiruvchi funksiya) esa asosiy masalani qismlarga ajratadi va ularning har birini alohida yechadi. Rekursiv algorutmlarning analizi anchayin murakkab. U masalani qismlarga bo’lish amallarini sonini, asosiy masalaning har bir qismida algoritmning bajarilishini, shu bilan birga ularning birlashmasini hisoblashni talab etadi. Qaysi instruksiyalarni hisoblash kerak? Bu savolga aniq javob mavjud emas, lekin aniq faktki – hisoblashda mavjud operatsiyalar(amallar)ni inobatga olish lozim. Ularga quyidagilarni kiritish mumkin:  Oddiy o’zlashtirish: а ← b ;  Massiv elementlarini indekslash (uning qiymatini aniqlash);  Arifmetik amallar: -, +, *, / ;  Solishtirish amallari: <, >, =, <=, >=, <> ;  Mantiqiy amallar: or, and, not . Algoritmning vaqt bo’yicha murakkabligiga kirish ma’lumotlarining hajmi sezilarli ta’sir ko’rsatadi. Unchalik kata bo’lmagan hajmdagi ma’lumotlarni qayta ishlashda ikkita turli algoritmning ishlash vaqti ahamiyatsizdek tuyulishi mumkin, ammo ma’lumotlar hajmining ortishi ularning bajarilish vaqtiga sezilarli darajada ta’sir ko’rsatishi mumkin. 3

Lekin vaqt bo’yicha murakkablik faqatgina hajmga emas, balki ma’lumotlarning qiymatiga, shuningdek ularning tushish(uchrash) tartibiga ham bog’liq. Masalan, ko’pchilik saralash algoritmlari agar massivning o’zi saralangan bo’lsa, massivni tartiblashga anchayin kam vaqt sarflaydi. Shu kabi holatlar sabab vaqt bo’yicha murakkablikni uch xil holatda ko’rib chiqiladi: yomon, yaxshi va o’rta. Yomon holat kirish ma’lumotlarining omadsiz kiritilishida ya’ni algoritm masalani yechish uchun maksimal sondagi elementar amallarni bajarishi to’g’ri kelish holatiga mos keladi. Yaxshi holatda aksincha kirish ma’lumotlari imkon qadar minimal sondagi amallarni bajarilishi ta’minlaydi. O’rta holat anchayin murakkab aniqlanadi. Kirish ma’lumotlari imkon darajasida guruhlarga ajratiladi. Keyin har bir guruhning qatnashish ehtimolligi aniqlanadi. Shundan so’ng, har bir guruhning ma’lumotlar bilan ishlashi bo’yicha algoritmning ishlash vaqti hisoblanadi. Bizni ko’pincha eng kam va eng ko’p holatlari ko’proq qiziqtiradi. Kiritiluvchi ma’lumotlarning hajmi katta bo’lganda biror masalaning ekzemplyar(nusxa) asosida bajariluvchi yechimi, algoritmlarning ishlash vaqti analizini solishtirish asimptotik tahlil deb yuritiladi. Asimptotik murakkabligi kamroq bo'lgan algoritm ko'proq samarador (effektiv) hisoblanadi. Asimptotik tahlilda algoritmning murakkabligi – bu algoritmning ma’lumotlari hajmi ortishi bilan algoritmning ishlash vaqtining tezkor ravishta ortishini belgilovchi funksiyadir. Asimptotik tahlilda asosiy uchraydigan o'sishni baholash funksiyalari bular:  (O-katta) – vaqtni o'sishini yuqori asimptotik baholash funksiyasi;  Ω (Omega) – vaqtni o'sishini quyi asimptotik baholash funksiyasi;  Θ (Teta) - vaqtni o'sishini quyi vayuqori asimptotik baholash funksiyasi. Bunda n – ma'lumotlarning hajmiy kattaligi bo'lsin. U holda f(n) algoritmning o’sish funksiyasini asimptotik jihatdan g(n) funksiya bilan chegaralash mumkin: Mazmuni Tavsifi f ( n ) ∈ Ο ( g ( n )) f yuqoridan g funksiya bilan doimiy ko'paytiruvchi aniqligigacha chegaralangan f ( n ) ∈ Ω( g ( n )) f quyidan g funksiya bilan doimiy ko'paytiruvchi aniqligigacha chegaralangan 4

f ( n ) ∈ Θ( g ( n )) f yuqori va quyidan g funksiya bilan chegaralangan Misol uchun, muassasaning tozalash vaqti uning maydoni kattaligiga chiziqli ravishta bog’liq ( Θ ( S )), ya’ni maydon kattaligining n marta ortishi bilan uni tozalash vaqti ham n marta ortadi. Telefon daftarchasidan ismni qidirishda agar chiziqli qidirish algoritmidan foydalanilsa, O(n) chiziqli vaqtni talab etadi. Agar ikkilik qidiruvdan foydalanilsa, u holda ( Ο (log 2 ( n ))) yozuvlar soniga logarifmik bog’liq bo’ladi. Biz O – funksiya bilan ko’proq kuzatuvlar olib boramiz. Keyingi kuzatishlarda algoritmlarning murakkabligi yuqori asimptotik chegara bilan beriladi. Asimptotik tahlilning muhim qoidalari: 1. O ( k * f ) = O ( f ) – doimiy ko’payuvchi k (konstanta) tashlab yuboriladi, chunki doimiy kirish ma’lumotlarining ortishi bilan uning ahamiyati yo’qoladi, masalan: O(9,1n) = O(n) 1. O ( f * g ) = O ( f )* O ( g ) – ikkita funksiya ko’paytmasining murakkabligini baholash ularning murakkabliklari ko’paytmasiga teng, masalan: O(5n*n) = O(5n)*O(n) = O(n)*O(n) = O(n*n) = O(n 2 ) 2. O ( f / g )= O ( f )/ O ( g ) – ikkita funksiyaning bo’linmasining murakkabligi ular murakkabliklarining bo’linmasiga teng, masalan: O(5n/n) = O(5n)/O(n) = O(n)/O(n) = O(n/n) = O(1) 3. O ( f + g ) teng O(f) va O(g) larning dominantiga – funksiyalar summasining murakkabligini baholash, birinchi va ikkinchi qo’shiluvchilarning dominant (hukmron) murakkabligini baholash bilan belgilanadi, masalan: O(n 5 +n 10 ) = O(n 10 ) Amallarning sonini sanash juda mayda ish, eng muhimi bu unchalik muhim emas. Yuqorida keltirilgan qoidalardan kelib chiqqan holda, algoritmning murakkabligini aniqlashda oldin bajarganimizdek amallarni sanash kerak emas, biz uchun algoritm (operator yoki operatorlar guruhi) konstruksiyasi qaysi murakkablik darajasiga mansubligini bilish kifoya. Bundan ma’lumki, sikl va rekursiyalarga ega bo’lmagan algoritm O(1) konstanta murakkabligiga ega. n ta iteratsiyani bajaruvchi siklning murakkabligi O(n) ga teng. Bitta n o’zgaruvchi qiymatiga bog’liq bo’lgan ichma ich joylashgan ikkita siklning konstruksiyasi kvadratik murakkablikka O(n 2 ) ega bo’ladi. Quyida eng ko’p uchraydigan murakkablik sinflari keltirilgan: 5