TANLOV BO’YICHA SARALASH. ALGORITMNING MURAKKABLIGINI TAHLIL QILISH 2

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

56.8359375 KB

Ko'chirib olish

TANLOV BO’YICHA SARALASH. ALGORITMNING
MURAKKABLIGINI TAHLIL QILISH
Mundarija
Kirish .................................................................................................................................................................. 2
1. Algoritmlarning asimptotik tahlili ................................................................................................................... 4
2. Saralash algoritmlari ....................................................................................................................................... 8
3. Ustuvor navbatlarni piramidada qurish .......................................................................................................... 9
4. TOPSHIRIQ .................................................................................................................................................... 16
5. Asimptotik Tahlil ........................................................................................................................................... 29
Xulosa .............................................................................................................................................................. 34
Adabiyotlar ro’yhati: ........................................................................................................................................ 35
1

Kirish
Qandaydir masalani xal 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 axamiyatga 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
2

ifodalangan chekli qoidalar majmui tushunilgan.Hozirda ham ixtiyoriy masalani
yechish uchun ma’lum qonun qoidalar sifatida fanda qo’llanilib kelinmoqda.
3

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: -, +, *, / ;
4

 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.
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
5

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
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:
6

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:
 O (1) – konstantali murakkablik ;
 О ( n ) – chiziqli murakkablik;
 О ( n а
) – polynomial murakkablik ;
 О (log( n )) – logarifmik murakkablik;
7

 O(n*log(n)) – kvazichiziqli murakkablik;
 O (2 n
) – eksponensial murakkablik ;
 O ( n !) – factorial murakkablik .
2. Saralash algoritmlari
Saralash algoritmlari – informatikada juda yaxshi o’rganilgan sohalardan biri
va u juda keng qamrovli qo’llanilish sohasiga ega. Ularni katta hajmdagi
ma’lumotlarni saqlash va qayta ishlash amallari bajariladigan har qanday joyda
uchratish mimkin. Ba’zi ma’lumotlarni qayta ishlash masalalari agar ma’lumotlar
saralangan bo’lsa oson yechiladi. Bunday masalalar ushbu laboratoriya ishida
ko’rib chiqiladi.
Saralash metodlari
Odatda saralash metodlarini ikkiga ajratishadi:
Ichki saralash –ma’lumotlar operativ xotirada joylashgan bo’lib, bunda
dasturning harakatlari sonini (solishtirish, solishtirishlar soni, elementlar
almashinuvi va b.qa metodlarga asoslangan) optimallashtirish muhim ahamiyat
kasb etadi;
Tashqi saralash – ma’lumotlar murojaatlarni sekinlashtiruvchi tashqi
hotirada (magnit lenta, baraban, disk va b.qa) joylashgan bo’lib, bunda aynan shu
qurilmaga murojaatlar sonini kamaytirish lozim.
Bu labaratoriya ishida ko’plab dasturchilar uchun amaliyotda muhim bo’lgan
massiv elementlarini ichki saralash algoritmlarini ko’rib chiqamiz.
Ta’kidlash joizki, surish orqali saralash algoritmini tashqi ma’lumotlarni
saralashda qo’llash ham qulay.
Qidirish algoritmlari
Qidirish algoritmlari bu berilgan qiymatni ma’lum algoritm asosida
elementlarning ichidan yoki elementlarning ma’lum bir qismidan qidirishni
amalga oshirish algoritmlari. Qidirish algoritmlarining bugungi kunga kelib ancha
metodlari ishlab chiqilgan. Qidirish algoritmlarini shartli ravishta tartiblanmagan
8

ma’lumotlar to’plami bilan va tartiblangan ma’lumotlar to’plami bilan ishlovchi
turlarga ajratish mumkin.
100% dasturchilar o’rganish mobaynida massivda biron elelment
mavjudligini tekshirish muammosiga duch keladi. Dasturlash tillarida bir qancha
qidirish algoritmlari mavjud. Ularning har birining ishlash prinsipi o’ziga xos va
albatta murakkablik jihatidan ham farqlanadi.
Ustuvor navbatlar
Ustuvor navbatlar (ing. Priority queue) – oddiy navbatlarga o’xshash ammo
bir qator xususiyatlarga ega abstract konteyner:
 Ustuvor navbatning har bir elementiga shu elementning ustuvorligini
belgilovchi qandaydir qiymat mos qo’yilgan. Prioritet bir biri bilan
solishtirish orqali kiritiladi;
 Ustuvor navbatdan element yechib olish funksiyasi qaysi elementning
prioriteti maksimal bo’lsa o’shani qaytaradi.
Ko’plab ilovalarda yozuvlarni ularning kalitlarini o’sish tartibi bo’yicha
qayta ishlashni talab qiladi, lekin bu qat’iy tartibda va hammasini birdaniga qilish
degani emas. Ko’pchilik hollarda yozuvlar biron to’plamda yig’iladi va keyin
maksimal kalitli yozuv qayta ishlanadi, shundan so’ng yana yozuvlarni yig’ish
yana davom ettirilishi, so’ngra joriy kalitdan kattaroq kalitga ega yozuv qayta
ishlanishi mumkin va h.k. Bunday ma’lumotlar strukturasi ustuvor navbat
(priority queue) deb yuritiladi. Ustuvor navbatlardan foydalanish oddiy
navbatlardan (eng eski element o’chiriladi) va steklardan (eng yangi element
o’chiriladi) foydalanish kabi, ammo ulardan unumli foydalanish murakkabroq.
3. Ust uv or nav bat larni piramidada qurish
Piramidaning muhim ustunligidan biri undagi qiymatlardan maksimali uning
uchida joylashgan bo’ladi. Piramidaning qayta tiklash up() va down() amallari
ko’chishlar sonini piramidaning uchidan oshmagan holda amalga oshiradi, bu esa
ustuvor navbatlarni samarali qo’llashga imkon yaratadi.
9

$Avvalo, bu qo’llash elementning tuzilmasini (chunki element faqatgina prioritetni emas balki qiymatni ham o’zida saqlaydi) tavsiflashni va piramidani hosil qiluvchi massivni e’lon qilishni talab qiladi. Piramidani qayta tiklash amallari priority maydonini solishtirishi lozim. Navbatning elementlari sonini saqlash uchun konstruktorda 0 qiymati bilan tashkil qilinadigan alohida size o’zgaruvchisi ajratiladi. static const int MAX_SIZE = 100; struct Elem { int val; int priority; Elem(int v = 0, int p = 0) { val = v; priority = p; } } a[MAX_SIZE]; int size; Elementlar qo’shish a[size] yacheykasida amalga oshiriladi. Qo’shimcha element kiritilgandan so’ng piramidaning asosiy xususiyati o’zgarishi mumkin, qo’shimcha ravishta up() protsedurasini chaqirish talab qilinadi. Qo’shimcha element kiritishning umumiy murakkabligi O(lonN) tashkil qiladi. void enqueue(int value, int priority) { if (size + 1 == MAX_SIZE) /* обработка ошибки - переполнение очереди */ 10$ $a[size++] = Elem(value, priority); up(size - 1); } Elementni o’chirishda quyidagicha yo’l tutish mumkin: piramidaning uchiga eng so’nggi elementni joylashtirish va uchun down() amalini bajarish. O’chirishning murakkabligi O(logN) ga teng. void enqueue(int value, int priority) { if (size + 1 == MAX_SIZE) /* обработка ошибки - переполнение очереди */ a[size++] = Elem(value, priority); up(size - 1); } Quyida ustuvor navbatning qo’llanilishi bo’yicha to’liq kod keltirilgan. Navbat elementlarining oshib ketish va bo’sh navbatdan element yechib olishga urunishlar assert (/<assert.h> yoki <cassert> sarlavha fayli) konstruksiyasi yordamida qilinadi. class PriorityQueue { static const int MAX_SIZE = 100; struct Elem { int val; 11$ $int priority; Elem(int v = 0, int p = 0) { val = v; priority = p; } } a[MAX_SIZE]; int size; void up(int i) { while (i != 0 && a[i].priority > a[(i - 1) / 2].priority) { swap(a[i], a[(i - 1) / 2]); i = (i - 1) / 2; } } void down(int i) { while (i < size / 2) { int maxI = 2 * i + 1; if (2 * i + 2 < size && a[2 * i + 2].priority > a[2 * i + 1].priority) maxI = 2 * i + 2; if (a[i].priority >= a[maxI].priority) 12$ $return; swap(a[i], a[maxI]); i = maxI; } } public: PriorityQueue() { size = 0; } void enqueue(int value, int priority) { assert(size + 1 < MAX_SIZE); a[size++] = Elem(value, priority); up(size - 1); } int dequeue() { assert(size > 0); swap(a[0], a[--size]); 13$ down(0);
return a[size];
}
bool isEmpty() {
return size == 0;
}
};
Quyida mavjud algoritmlarning asimptotik tahlilini jadvallar bilan ko’rib
chiqamiz. Bunda:
Yaxshi O’rta Yomon
Saralash algoritmlari tahlili:
Algoritm Ma’lu
motlar
tuzilma
si Vaqt bo’yicha murakkabligi Qo’shimc
ha
ma’lumot
lar
Yaxshi O’rta Yomon Yomon
holatda
Tezkor saralash Massiv O(n
log(n)) O(n
log(n)) O(n 2
) O(n)
14

down(0);
return a[size];
}
bool isEmpty() {
return size == 0;
}
};
Quyida mavjud algoritmlarning asimptotik tahlilini jadvallar bilan ko’rib
chiqamiz. Bunda:
Yaxshi O’rta Yomon
Saralash algoritmlari tahlili:
Algoritm Ma’lu
motlar
tuzilma
si Vaqt bo’yicha murakkabligi Qo’shimc
ha
ma’lumot
lar
Yaxshi O’rta Yomon Yomon
holatda
Tezkor saralash Massiv O(n
log(n)) O(n
log(n)) O(n 2
) O(n)
14

Surish orqali
saralash Massiv O(n
log(n)) O(n
log(n)) O(n
log(n)) O(n)
Piramidali
saralash Massiv O(n
log(n)) O(n
log(n)) O(n
log(n)) O(1)
Pufakchali
saralash Massiv O(n) O(n 2
) O(n 2
) O(1)
Qo’yish orqali
saralash Massiv O(n) O(n 2
) O(n 2
) O(1)
Tanlash orqali
saralash Massiv O(n 2
) O(n 2
) O(n 2
) O(1)
Blokli saralash Massiv O(n+k) O(n+k) O(n 2
) O(nk)
Razryad bo’yicha
saralash Massiv O(nk) O(nk) O(nk) O(n+k)
15

4. TOPSHIRIQ
1 – topshiriq.
Berilgan variant bo’yicha C++ (Python, Java) tilida har uchala saralash
metodini bajaring va jadval shaklida solishtirib analiz qiling.
Birinchi topshiriq bo’yicha variantlar
Ro’yhat
bo’yicha
variant
nomeri Massivni
to’ldirish Saralash
metodi Har bir metod uchun massivdagi
elementlarning soni
1,2,3 Tasodifiy
elementlar
bilan
to’ldirilgan
massiv Sanash
Pufakchali
Shell 300 1200 4000
4,5,6 Tasodifiy
elementlar
bilan
to’ldirilgan
massiv Surish
Tezkor
Tanlash 400 1300 4500
7,8,9 Tasodifiy
elementlar
bilan
to’ldirilgan
massiv Pufakchali
Tezkor
Kiritish 200 1500 4000
10,11,12 Tasodifiy Surish 500 1600 5000
16

elementlar
bilan
to’ldirilgan
massiv Sheyker
Tezkor
13,14,15 Tasodifiy
elementlar
bilan
to’ldirilgan
massiv O’rniga
qo’yish
Pufakchali
Tanlash 350 2000 6000
16,17,18 Tasodifiy
elementlar
bilan
to’ldirilgan
massiv Sheyker
Tezkor
Surish 450 1800 5500
2 – topshiriq
C++ (Python, Java) tilida quyida keltirilgan amallarni bajargan holda ustuvor
navbat tashkil qiling:
 Berilgan N ta elementdan iborat ustuvor navbat hosil qiling;
 Yangi element qo’shing;
 Eng katta elementni yechib oling;
 Berilgan qandaydir elementning prioritetini o’zgartiring;
 Berilgan qandaydir elementni yechib oling;
 Ikkita ustuvor navbatni birlashtiring.
Algoritm - bu belgilaydigan cheklangan qoidalar to plami, muayyanʻ
vazifalar to plamini hal qilish bo yicha amallar ketma-ketligi va beshta
ʻ ʻ
muhim xossaga ega: aniqlik, tushunarlilik, kiritish, chiqarish, samaradorlik
Algoritm qadami – Algoritmda bajarilishi tugallangan amallar ketmaketligi.
17

Algoritmning vaqt bo yicha qiyinligi – Algoritm sarflanayotgan vaqtʻ
masalaning o lchami funksiyasi deyiladi.
ʻ
Algoritmlarning murakkabligini tahlil qilish. Misollar
01/06/2015 algoritmlar
Algoritm - bu o'zgaruvchan boshlang'ich ma'lumotlardan kerakli natijaga olib
keladigan hisoblash jarayonini noyob tarzda belgilaydigan aniq retseptdir [1].
Algoritmlarni ishlab chiqishda hisob-kitoblarni amalga oshirish uchun zarur
bo'lgan resurslarni baholay olish juda muhim, baholash natijasi murakkablik
(mehnat sarfi) funktsiyasidir. Hisoblangan resurs ko'pincha protsessor vaqti
(hisoblash murakkabligi) va xotira (algoritmning xotira murakkabligi)
hisoblanadi. Baholash bajarilish vaqtini bashorat qilish va algoritmlarning ish
faoliyatini solishtirish imkonini beradi.
Tarkib:
RAM modeli (tasodifiy kirish mashinasi)
Hisoblash operatsiyalari. Kirish sinflari
Asimptotik belgi
Algoritm tahliliga misollar
Algoritmlarni tahlil qilish uchun matematik apparat
Xulosa formulalari
Xulosa va integratsiya
Algoritmlarning murakkabligini taqqoslash. chegaralar
Logarifmlar va algoritmlarning murakkabligi
Tahlil natijalari. Izohlar. Adabiyot
RAM modeli (tasodifiy kirish mashinasi)
Har bir hisoblash qurilmasi o'ziga xos xususiyatlarga ega bo'lib, bu hisoblash
davomiyligiga ta'sir qilishi mumkin. Odatda algoritmni loyihalashda
protsessor keshining hajmi yoki operatsion tizim tomonidan amalga
18

oshirilgan ko'p vazifalar turi kabi tafsilotlar hisobga olinmaydi. Algoritmlarni
tahlil qilish tasodifiy xotira (RAM) mashinasi deb ataladigan mavhum
kompyuter modelida amalga oshiriladi.
Model xotira va protsessordan iborat bo'lib, ular quyidagicha ishlaydi:
xotira hujayralardan iborat bo'lib, ularning har biri manzilga ega va
ma'lumotlarning bir elementini saqlashi mumkin;
har bir xotiraga kirish manzillangan yacheykaning sonidan qat'iy nazar bir
birlik vaqtni oladi;
xotira miqdori har qanday algoritmni bajarish uchun etarli;
protsessor har qanday elementar amalni (asosiy mantiqiy va arifmetik
amallar, xotiradan o‘qish, xotiraga yozish, kichik dasturni chaqirish va h.k.)
bir vaqtning o‘zida bajaradi;
sikl va funksiyalar elementar amallar hisoblanmaydi.
Bunday model haqiqiy kompyuterdan uzoq bo'lishiga qaramay, u
algoritmlarni tahlil qilish uchun juda mos keladi. Algoritm ma'lum bir
kompyuter uchun amalga oshirilgandan so'ng, siz profillash va past
darajadagi optimallashtirishni amalga oshirishingiz mumkin, ammo bu
algoritmni optimallashtirish emas, balki kodni optimallashtirish bo'ladi.
Hisoblash operatsiyalari. Kirish sinflari
Murakkablikni baholashning bir usuli ([Math Processing Error]) bajarilgan
operatsiyalar sonini hisoblashdir. Masalan, massivning minimal elementini
topish algoritmini ko'rib chiqing.
Boshlash; N elementli massivning minimal elementini topish
min := massiv[1]
i uchun 2 dan N gacha:
agar massiv[i] < min
min := massiv[i]
nihoya; qaytish min
19

Ushbu algoritmni bajarishda quyidagilar amalga oshiriladi:
N — 1 sikl hisoblagichiga yangi qiymat berish operatsiyasi i;
N - N qiymati bilan 1 hisoblagich taqqoslash operatsiyasi;
N — massiv elementlarini min qiymati bilan solishtirishning 1 operatsiyasi;
1 dan N gacha o'zgaruvchiga qiymat berish operatsiyalari min.
Amaliyotlarning aniq soni qayta ishlanayotgan ma'lumotlarga bog'liq
bo'ladi, shuning uchun eng yaxshi, eng yomon va o'rtacha holatlar haqida
gapirish mantiqan. Shu bilan birga, har doim eng yomon holatga alohida
e'tibor qaratiladi, shu jumladan "yomon" ma'lumotlar tajovuzkor tomonidan
ataylab kirishga yuborilishi mumkin.
O'rtacha holat tushunchasi ma'lumotlar to'plamining bir xil ehtimoli
borligini taxmin qilgan holda algoritmning harakatini baholash uchun
ishlatiladi. Biroq, bunday baholash ancha murakkab:
bir guruhning har qanday ma'lumotlar to'plami uchun algoritmning
murakkabligi ([Math Processing Error]) bir xil bo'lishi uchun dastlabki
ma'lumotlar guruhlarga bo'linadi;
to'plamlarning umumiy sonidagi guruh ma'lumotlar to'plamining ulushiga
asoslanib, har bir guruh uchun ehtimollik hisoblanadi ([Math Processing
Error]);
o'rtacha ish ball quyidagi formula bo'yicha hisoblanadi: [Math Processing
Error].
Asimptotik belgi
Amallar sonini hisoblash algoritmlarning samaradorligini solishtirish
imkonini beradi. Biroq, shunga o'xshash natijani oddiyroq usulda olish
mumkin. Tahlil qayta ishlangan ma'lumotlarning etarlicha katta hajmini
([Math Processing Error]) kutish bilan amalga oshiriladi, shuning uchun
operatsiyalarning aniq soni emas, balki murakkablik funktsiyasining o'sish
tezligi muhim ahamiyatga ega.
20

O'sish sur'atini tahlil qilishda ifodadagi doimiy shartlar va omillar
e'tiborga olinmaydi, ya'ni. [Math Processing Error] va [Math Processing
Error] funktsiyalari o'sish tezligi bo'yicha ekvivalentdir. Muhim bo'lmagan
a'zolar faqat "to'lqinlilik" ni qo'shadi, bu esa tahlilni murakkablashtiradi.
Algoritmlarni baholashda quyidagi funktsiyalar sinflarini aniqlaydigan
maxsus asimptotik belgilar qo'llaniladi:
[Math Processing Error] - funktsiyalar g dan sekinroq o'sadi;
[Math Processing Error] - funksiyalar g dan tezroq o'sadi;
[Math Processing Error] - funktsiyalar g bilan bir xil tezlikda o'sadi.
[Math Processing Error] yozuvi f funksiyasi [Math Processing Error] sinfiga
tegishli ekanligini bildiradi, ya'ni. f funktsiyasi yuqoridan argumentning
etarlicha katta qiymatlari uchun g funktsiyasi bilan chegaralangan.
[Matematik ishlov berish xatosi].
g funksiyani pastdan f funksiya bilan chegaralanishi quyidagicha
yoziladi: [Math Processing Error]. [Math Processing Error] va [Math
Processing Error] belgilari bir-birini almashtiradi: [Math Processing Error].
asimptotik belgi_Omega "Katta O" va "Katta Omega" asimptotik belgilari.
Agar f va g funktsiyalari bir xil o'sish tezligiga ega bo'lsa ([Matematik
ishlov berish xatosi]), u holda [Math Processing Error] va [Math Processing
Error] musbat konstantalar mavjud bo'lib, [Math Processing Error]. Bu bilan
[Matematik ishlov berish xatosi].
asimptotik notation_Theta
"Theta big" asimptotik belgisi
Algoritm tahliliga misollar
Yuqorida keltirilgan massivning minimal elementini topish algoritmi
siklning N ta takrorini bajaradi. Har bir iteratsiyaning murakkabligi massiv
elementlari soniga bog'liq emas, shuning uchun u [Math Processing Error]
21

murakkabligiga ega. Shu munosabat bilan butun algoritmning yuqori
chegarasi [Math Processing Error] hisoblanadi. Xuddi shunday, pastroq
murakkablik bahosi hisoblab chiqiladi va u yuqoriga to'g'ri kelishi sababli,
biz [Math Processing Error] ni tasdiqlashimiz mumkin.
Pufakchali tartiblash algoritmi ikkita ichki o'rnatilgan halqadan
foydalanadi. Ichki juft elementlarda ketma-ket taqqoslanadi va agar
elementlar noto'g'ri tartibda ekanligi aniqlansa, almashtirish amalga
oshiriladi. Tashqi sikl massivda kerakli tartibni buzadigan kamida bitta juft
elementlar mavjud bo'lguncha bajariladi [2].
Boshlash; N ta elementdan iborat pufakchali tartiblash massivi
nPairs := N; juft elementlar soni
hasSwapped := false; hozirgacha hech bir er-xotin qoidalarni buzmagan
1 dan nPairs-1 gacha bo'lgan barcha i uchun:
agar massiv[i] > massiv[i+1] bo'lsa, unda: almashtirish(massiv[i],
massiv[i+1]); elementlarni almashtirish
hasSwapped := true; almashtirish topildi
nPairs := nPairs - 1; eng katta element oxirida joylashtirilishi kafolatlanadi
agar hasSwapped = true - keyin 3-bosqichga o'ting
nihoya; massiv tartiblangan
Almashtirish funktsiyasining murakkabligi massivdagi elementlar soniga
bog'liq emas, shuning uchun u [Math Processing Error] sifatida baholanadi.
Ichki tsiklning bajarilishi natijasida eng katta element tartiblanmagan qism
massivining oxiriga siljiydi, shuning uchun N ta bunday chaqiruvdan keyin
massiv baribir tartiblanadi. Agar massiv tartiblangan bo'lsa, ichki tsikl faqat
bir marta bajariladi.
Shunday qilib:
[Matematik ishlov berish xatosi];
[Matematik ishlov berish xatosi].
22

Tanlovni saralash algoritmida massiv aqliy jihatdan tartiblangan va xom
qismlarga bo'linadi. Har bir bosqichda massivning tartiblanmagan qismidan
minimal element tanlanadi va tartiblangan qismga qo'shiladi [2].
Boshlash; tanlash_sort - N elementli massivni tanlash usuli bo'yicha saralash
1 dan N gacha bo'lgan barcha i uchun:
imin := indMin(massiv, N, i)
almashtirish (massiv [i], massiv [imin])
nihoya; massiv tartiblangan
Massivning tartiblanmagan qismining eng kichik elementini topish uchun
massivni, massivning o‘lchamini va izlash uchun joy raqamini oladigan
indMin funksiyasidan foydalaniladi. Bu funksiyaning murakkabligini tahlil
qilish min funksiya uchun bajarilgani kabi amalga oshirilishi mumkin -
amallar soni qayta ishlangan elementlar soniga chiziqli bog'liq: [Math
Processing Error].
Tanlash algoritmining eng oddiy holati - bu minimal (yoki maksimal)
elementni ro'yxat bo'ylab takrorlash orqali topish, ishlaydigan minimal -
hozirgacha minimal - (yoki maksimal) ko'rsatkichlarini kuzatib borish va
tanlov saralash bilan bog'liq deb ko'rish mumkin. Aksincha, tanlov
algoritmining eng qiyin holati bu mediani topishdir. Aslida, medianlar
medianasida bo'lgani kabi, umumiy tanlov algoritmini tuzishda ixtisoslashgan
median-tanlov algoritmidan foydalanish mumkin. Tanlovning eng taniqli
algoritmi Quickselect bo'lib, u Quicksort bilan bog'liq; Quicksort singari, u
o'rtacha (asimptotik) maqbul o'rtacha ko'rsatkichga ega, ammo eng yomon
ko'rsatkichlar, ammo uni eng yomon ko'rsatkichlarni ham berish uchun
o'zgartirish mumkin.
Ro'yxat yoki qatorni saralash orqali kerakli elementni tanlab,
saralashga saralashgacha qisqartirish mumkin. Ushbu usul bitta elementni
tanlash uchun samarasiz, ammo massivdan ko'plab tanlovlarni o'tkazish kerak
23

$bo'lganda samarali bo'ladi, bu holda faqat bitta boshlang'ich, qimmat saralash kerak bo'ladi, undan keyin ko'plab arzon tanlov operatsiyalari - massiv uchun O (1) , tasodifiy kirishning etishmasligi sababli, saralangan bo'lsa ham, bog'langan ro'yxatda tanlov O (n) bo'lsa ham. Umuman olganda, saralash uchun O (n log n) vaqt kerak bo'ladi, bu erda n - ro'yxatning uzunligi, ammo pastki chegara radiaks sort va count sort kabi taqqoslanmagan tartiblash algoritmlari bilan mumkin bo'lsa ham. Butun ro'yxatni yoki qatorni saralash o'rniga, eng kichik yoki k kattaroq elementlarni tanlash uchun qisman saralashdan foydalanish mumkin. Keyinchalik kichkina k (eng katta element), qisman tartiblangan ro'yxatning eng kattasi (resp., Eng kichik element) - bu O (1) qatorga kirish uchun va O (k) - ro'yxatga kirish uchun Tartibsiz qisman saralash Agar qisman saralash eng kichik k elementlar qaytarilishi uchun yumshatilsa, lekin tartibda bo'lmasa, O (k log k) omilini yo'q qilish mumkin. Qo'shimcha maksimal tanlov (O (k) vaqtni olish) talab qilinadi, ammo {\ displaystyle k \ leq n} k \ leq n bo'lgani uchun, bu hali ham O (n) ning asimptotik murakkabligini keltirib chiqaradi. Darhaqiqat, bo'linishga asoslangan tanlash algoritmlari k-chi elementning o'zi va k-ning eng kichik elementlarini oladi (boshqa elementlar tartibda emas). Buni O (n) vaqt ichida amalga oshirish mumkin - Quickselectning o'rtacha murakkabligi va eng yomon holatdagi murakkab bo'linmalarga asoslangan tanlash algoritmlari. Aksincha, tanlash algoritmini hisobga olgan holda, ro'yxatni takrorlash va k elementidan kam bo'lgan barcha elementlarni yozish orqali O (n) vaqt ichida tartibsiz qisman saralashni (k kichik elementlar, tartibda emas) osongina olish mumkin. Agar bu k - 1 dan kam elementga olib keladigan bo'lsa, qolgan elementlar k elementiga tenglashadi. Elementlarning tengligi ehtimoli tufayli ehtiyot bo'lish kerak: k elementga teng yoki teng bo'lmagan barcha 24$

elementlarni o'z ichiga olmaydi, chunki k elementdan kattaroq elementlar
ham unga teng bo'lishi mumkin.
Shunday qilib tartibsiz qisman saralash (eng past k elementlar, lekin
buyurtma qilinmagan) va k elementni tanlash juda o'xshash muammolar. Ular
nafaqat bir xil asimptotik murakkablikka ega (O (n)), balki ikkalasining ham
echimini boshqasiga to'g'ridan-to'g'ri algoritm (max k elementlarini topish
yoki ro'yxatning elementlarini filtrlash) yordamida hal qilish mumkin. k-
element qiymatining kesilishi).
Qisman tanlov saralash
Qisman saralash orqali tanlashning oddiy misoli bu qisman tanlash
saralashidan foydalanishdir.
Minimal (maksimal maksimal) ni topish uchun aniq chiziqli vaqt algoritmi -
ro'yxat bo'yicha takrorlash va shu paytgacha minimal (maksimal maksimal)
elementni kuzatib borish - 1 ta eng kichik elementni tanlaydigan qisman
tanlov saralashi sifatida qaralishi mumkin. Shu bilan birga, boshqa ko'plab
qisman navlar, shuningdek, k = 1 holati uchun ushbu algoritmni qisqartiradi,
masalan, qisman yig'ma tartiblash.
Umuman olganda qisman tanlov saralashi O (kn) vaqtni talab qiladigan oddiy
tanlov algoritmini beradi. Bu asimptotik jihatdan samarasiz, ammo agar k
kichik bo'lsa
va uni bajarish oson bo'lsa, etarli darajada samarali bo'lishi mumkin. Aniq
qilib aytganda, biz minimal qiymatni topamiz va uni boshiga o'tkazamiz,
qolgan elementlarni k elementlar yig'ilguncha takrorlaymiz va keyin k
elementni qaytaramiz. Qisman tanlov asosida saralash algoritmi:
function select(list[1..n], k)
for i from 1 to k
minIndex = i
minValue = list[i]
25

for j from i+1 to n do
if list[j] < minValue then
minIndex = j
minValue = list[j]
swap list[i] and list[minIndex]
return list[k]
Algoritmni tahlil qilishdan maqsad – algoritmga ma’lumotlarni aniq
muvaffaqiyatli qayta ishlash uchun kerak bo’ladigan xotira hajmi va ishlash
vaqtining baholari va chegaralarini olish. Bir masalani yechadigan ikki algoritmni
taqqoslash uchun qandaydirsonli mezon topish kerak.
Faraz qilaylik, A – qandaydir bir turkumdagi masalalarni yechadigan algoritm, n –
esa shu turkumdagi alohida bir masalaning kattaligi.Umumiy holda, n – oddiy
skalyar yoki massiv yoki kiritiladigan ketma – ketlikning uzunligi bo’lishi
mumkin.
( n )
f(A)
- n kattalikdagi ixtiyoriy masalani yechadigan algoritm A bajarish
kerak bo’lgan asosiy amallarni (qo’shish, ayirish, taqqoslash,…) yuqori
chegarasini beradigan ishchi funksiya. Algoritmningsifatini baholash uchun
quyidagi mezonni ishlatamiz.
Agar
26

( n)
f(A)
o’sish tartibi n dan bog’liq bo’lgan polinomdan katta bo’lmasa, A
algoritm polinomial deb aytiladi, aks holda algoritm A eksponensial hisoblanadi.
Shular bilan birgalikda tahlil jarayonida ko’p matematik fanlarda standart bo’lgan
iboralar ishlatiladi.
ilda Kompyuter fanlari, algoritmlarni tahlil qilish ni topish jarayoni
hisoblash murakkabligi algoritmlar - vaqt, saqlash yoki boshqa manbalar miqdori
ularni ijro eting. Odatda, bu a ni o'z ichiga oladi funktsiya algoritm kiritish
uzunligini va uni bajaradigan qadamlar soniga bog'laydigan (uning vaqtning
murakkabligi) yoki u foydalanadigan saqlash joylari soni (uning kosmik
murakkablik). Algoritm ushbu funktsiya qiymatlari kichik bo'lganda yoki kirish
hajmining o'sishiga nisbatan sekin o'sganda samarali bo'ladi deyiladi. Xuddi shu
uzunlikdagi turli xil yozuvlar algoritmning xatti-harakatlariga olib kelishi mumkin,
shuning uchun eng yaxshi, eng yomon va o'rtacha ish tavsiflarning barchasi amaliy
qiziqish uyg'otishi mumkin. Agar boshqacha ko'rsatilmagan bo'lsa, algoritmning
ishlashini tavsiflovchi funktsiya odatda yuqori chegara, algoritmga eng yomon
holatlardan aniqlandi.
Algoritmlarni tahlil qilish" atamasi tomonidan kiritilgan Donald Knuth.[1]
Algoritmni tahlil qilish keng doiraning muhim qismidir hisoblash murakkabligi
nazariyasi, bu berilganni hal qiladigan har qanday algoritm uchun zarur bo'lgan
manbalar uchun nazariy baholarni beradi hisoblash muammosi. Ushbu taxminlar
izlashning oqilona yo'nalishlari to'g'risida tushuncha beradi samarali algoritmlar.
Algoritmlarni nazariy tahlil qilishda ularning murakkabligini asimptotik ma'noda
baholash, ya'ni o'zboshimchalik bilan katta kirish uchun murakkablik funktsiyasini
27

baholash odatiy holdir. Big O notation, Katta-omega yozuvlari va Big-teta yozuvi
shu maqsadda ishlatiladi. Masalan; misol uchun, ikkilik qidirish qidirilayotgan
tartiblangan ro'yxat uzunligining logarifmiga mutanosib bo'lgan bir necha
bosqichda yoki O (log (n)) da, so'zma-so'z " logaritmik vaqt". Odatda asimptotik
taxminlar har xil bo'lgani uchun ishlatiladi amalga oshirish bir xil algoritm
samaradorligi bilan farq qilishi mumkin. Ammo berilgan algoritmni istalgan ikkita
"oqilona" amalga oshirish samaradorligi a deb nomlangan doimiy multiplikativ
omil bilan bog'liq. yashirin doimiy.
Ba'zida samaradorlikning aniq (asimptotik bo'lmagan) o'lchovlari hisoblab
chiqilishi mumkin, ammo ular odatda algoritmni amalga oshirishda ma'lum
taxminlarni talab qiladi, deyiladi hisoblash modeli. Hisoblash modeli an nuqtai
nazaridan aniqlanishi mumkin mavhum kompyutermasalan, Turing mashinasi, va /
yoki ma'lum bir operatsiyalar birlik vaqtida bajarilishini e'lon qilish orqali,
masalan, agar biz ikkilik qidiruv qo'llanadigan tartiblangan ro'yxatda n va biz
ro'yxatdagi elementni har bir qidirishni birlik vaqtida, so'ngra eng ko'p jurnalda
bajarilishi mumkinligiga kafolat beramiz2 n Javobni qaytarish uchun + 1 marta
birlik kerak.
Ikkita algoritm berilgan, qaysi biri yaxshiroq ekanligini qanday aniqlash mumkin?
Eng oddiy yo'li, dasturni ikkita kompyuterda ishga tushirib dasturga turli sonlar
kiritish bilan tekshirib ko'rish va qaysi birini kam vaqt olayotganini aniqlash.
Ammo, bu usulning juda ko'p kamchiliklari mavjud:
1) Ba'zi sonlar uchun birinchi algoritm , ba'zi sonlar uchun esa ikkinchi algoritm
tezroq ishlashi mumkin.
2) Ba'zi sonlar uchun birinchi kompyuterdagi birinchi algoritm, ba'zi sonlar uchun
esa ikkinchi algoritm boshqa kompyuterda tezroq ishlashi mumkin.
28

Algoritmni a simptotik Tahlil qilish yuqoridagi muammolarni bartaraf etishga
yordam beradi. Algoritmni asimptotik Tahlil qilishda biz algoritmga turli sonlar
kiritilganda u qanday unumdorlik ko'rsatishini baholaymiz . Biz algoritmga
kiritilayotgan sonlar ortishi bilan uning ishlash vaqti (yoki xotiradan joy
egallashi) qanday ortishi ni o'lchaymiz (algoritmni ishlash vaqt davomiyligi
qanchaligini emas).
Asimptotik Tahlil algoritmni baholash uchun eng yaxshi variantmi?
Asimptotik Tahlil 100% to'g'ri tahlil qilish imkonini bermaydi, ammo algoritmini
asimptotik Tahlil qilish mavjud boshqa barcha Tahlil yo'llari ichida eng yaxshisi.
Misol uchun, ikkita saralash algoritm bor deb tassavur qilaylik, birinchisiga n son
kiritilganda uning ishlash vaqti 100nLog(n ) funksiya asosida , ikkinchisiga n son
kiritilganda uning ishlash vaqti 2nLog(n) funksiya asosida ortsin. Bu
algoritmlarning unumdorligi asimptotik Tahlilda teng deb hisoblanadi (o'sish
tartibi nLog(n)), chunki asimptotik Tahlilda konstanta koeffisiyentlar hisobga
olinmaydi.
5. Asimptotik Tahlil
O'tgan postda biz asimptotik Tahlil nima ekanligi bilan tanshgan edik, Ushbu
postda biz chiziqli qididiruv algoritmini asimptotik Tahlil qilamiz.
Algoritmni Tahlil qilishda 3 xil holat bo'lishi mumkin:
1) Eng yomon holat
2) O'rtacha holat
29

3) Eng zo'r holat
Quyida chiziqli qidiruv algoritimining realizatsiyasi keltirilgan:
# include
int search ( int arr[], int n, int x)
{
int i;
for (i=0; i
{
if (arr[i] == x)
return i;
}
return -1;
}
int main ()
{
int arr[] = {1, 10, 30, 15};
30

int x = 30;
int n = sizeof (arr)/ sizeof (arr[0]);
printf ("%d soni %d inchi indexda topildi", x, search(arr, n, x));
getchar();
return 0;
}
Eng yomon holat
Eng yomon holatda biz algoritmni eng ko'p vaqt oladigan holatini qaraymiz. Bu
holat — eng baland chegara ( Upper bound ) deb ham ataladi. Chiziqli qidiruv
algoritmida eng yomon holat — qidirilayotgan x son arr massivda mavjud
bo'lmasligi. Chunki, agar arr massivda qidirilayotgan element mavjud bo'lmasa,
search() funksiyasi massivni barcha elementlarini bilan bitta-bitta qarab chiqadi.
Ushbu turdagi Tahlil eng keng foydalaniladi.
O'rtacha holat
O'rtacha holatda algoritmni ishlash vaqtini topish uchun , barcha sonlarni topish
uchun ketgan vaqtlarni (har bir sonni alohida-alohida topishga ketgan vaqtlar) o'rta
arifmetigi olinadi. Odatda amaliyotda, bu Tahlil juda ham ko'p ishlatilmaydi,
chunki bu holtda biz programma qabul qilishi mumkin bo'lgan barcha qiymatlarni
bilishimiz kerak bo'ladi.
Eng zo'r holat
Eng zo'r holat bu algoritmni bajarilishi uchun ketgan eng kam vaqtli holatdir.
Chiziqli qidiruv algoritimida, agar qidirilayotgan son massivda birinchi bo'lib
turgan bo'lsa sodir bo'ladi. Bu turdagi Tahlil amaliyotda deyarli umuman
ishlatilmaydi, chunki eng zo'r holat faqat shartli sonlardagina bajarilishi mumkin.
31

Esda tuting: Algoritmlarni asimptotik Tahlil qilishda odatda eng yomon
holat Tahlilidan foydalaniladi. Ya'ni algoritmning ishlash vaqti uning eng yomon
holati bilan baholanadi.
Algoritmlarni tahlil qilishda notatsiya tizimi
Algoritmning murakkabligini batafsilroq tahlil qilishda , N uzunlikning bitta
kirishida algoritm tomonidan bajarilgan elementar operatsiyalar soni har doim ham
bir xil uzunlikning boshqa kiritishida bajarilgan ishlar soni bilan bir xil emasligi
ayon bo'ladi. Bu ushbu algoritmning murakkablik funktsiyasining sobit
uzunlikdagi ma'lumotlarga xatti-harakatlarini aks ettiruvchi maxsus belgi qo'yish
zarurligiga olib keladi.
D
A rasmiy tizimda berilgan ushbu vazifaning o'ziga xos muammolarining to'plami
bo'lsin. D D
A muayyan muammoning vazifasi bo'lsin va | D | = N. Umumiy holda,
N kuchining barcha o'ziga xos muammolarini o'z ichiga olgan D
A to'plami mavjud:
ushbu to'plamni DN tomonidan belgilang:
D
N = {D D
N ,: |D| = N} ;
tomonidan o'rnatilgan DN quvvatini belgilang
M
DN > M
DN = |D
N |.
Keyinchalik, mazmunli ravishda , N o'lchovining turli muammolarini echgan holda,
ushbu algoritm ba'zi hollarda eng ko'p operatsiyalarni bajaradi, ba'zi holatlarda esa
eng kam sonli operatsiyalarni bajaradi. Biz quyidagi belgini olib boramiz:
1. F
a (N) - N o'lchovining aniq muammolarini hal qilish uchun A
algoritmi tomonidan bajariladigan operatsiyalarning eng katta miqdori:
F
a (N) = max {F
a (D)} - eng yomon ish D
N
32

2. F
a (N) - - eng yaxshi holat - N o'lchovining aniq muammolarini hal qilish
uchun A algoritmi tomonidan bajariladigan operatsiyalarning eng kam
soni:
F
a (N) = min {F
a (D)} - eng yaxshi holat D
N
3. F
a (N) - o'rtacha holat bu N o'lchovining aniq muammolarini echish
uchun A algoritmi tomonidan bajarilgan operatsiyalarning o'rtacha
soni:
33

Xulosa
Xulosa qilib shuni aytamanki Tanlov bo’yicha saralashni foydali tarafi biz ko’p
hollarda bir nechta algoritmlardan foydalanashimizga to’g’ri keladi usha payt
algoritmlarning barchasi to’g’ri yechimga olib borsada biz ulardan eng optimal
metodni tanlashimiz lozim.
Optimalikning kriteriyasi bu algoritmning burakkabligi hisoblanadi. Algoritm
murakkabligi odatda ikkiga bo’linadi ya’ni vaqt va hajm bo’yicha murakkablikka
ajratadi. Algoritm murakkabligi qoidasi quyidagicha ya’ni – bu algoritmning
ma’lumotlari hajmi ortishi bilan algoritmning ishlashi vaqtining tezkor ravishda
ortishini belgilovchi funksiya hisoblanadi.
Saralash metodlari ikkiga ajratiladi: ichki saralash va tashqi saralash .
Ichki saralash –ma’lumotlar operativ xotirada joylashgan bo’lib, bunda
dasturning harakatlari sonini (solishtirish, solishtirishlar soni, elementlar
almashinuvi va b.qa metodlarga asoslangan) optimallashtirish muhim ahamiyat
kasb etadi;
Tashqi saralash – ma’lumotlar murojaatlarni sekinlashtiruvchi tashqi
hotirada (magnit lenta, baraban, disk va b.qa) joylashgan bo’lib, bunda aynan shu
qurilmaga murojaatlar sonini kamaytirish lozim.
Algoritmninga murakkabligini tahlil qilishni uch xil holatda tahlil qilamiz ya’ni:
Eng yomon holat, o’rtacha holat va eng yaxshi holat.
Eng yomon holatda biz algoritm eng ko’p vaqt sarflaydiganiga qaraymiz.
O'rtacha holatda algoritmni ishlash vaqtini topish uchun , barcha sonlarni topish
uchun ketgan vaqtlarni (har bir sonni alohida-alohida topishga ketgan vaqtlar) o'rta
arifmetigi olinadi.
Eng yaxshi holat bu algoritmni bajarilishi uchun ketgan eng kam vaqtli holatdir
34

Adabiyotlar ro’yhati:
1. Абрамов С.А. Лекции о сложности алгоритмов.- М.: МЦНМО, 2009.-
256 с.
2. Дональд Кнут Искусство программирования, том 1. Основные
алгоритмы— 3-е изд. — М.: «Вильямс», 2006. — С. 720.
3. Кнут В. Искусство программирования. Т.3. Сортировка и поиск. – 2-е
изд. - Издательский дом “Вильямс”, 2000.
4. Вирт Н. Алгоритмы и структуры данных. Пер. с англ. – М.: Мир, 1989.
– 360.
5. Носов В.А. Основы теории алгоритмов и анализа их сложности. – М.,
1992.
35

TANLOV BO’YICHA SARALASH. ALGORITMNING MURAKKABLIGINI TAHLIL QILISH Mundarija Kirish .................................................................................................................................................................. 2 1. Algoritmlarning asimptotik tahlili ................................................................................................................... 4 2. Saralash algoritmlari ....................................................................................................................................... 8 3. Ustuvor navbatlarni piramidada qurish .......................................................................................................... 9 4. TOPSHIRIQ .................................................................................................................................................... 16 5. Asimptotik Tahlil ........................................................................................................................................... 29 Xulosa .............................................................................................................................................................. 34 Adabiyotlar ro’yhati: ........................................................................................................................................ 35 1

Kirish Qandaydir masalani xal 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 axamiyatga 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 2

ifodalangan chekli qoidalar majmui tushunilgan.Hozirda ham ixtiyoriy masalani yechish uchun ma’lum qonun qoidalar sifatida fanda qo’llanilib kelinmoqda. 3

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: -, +, *, / ; 4

 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. 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 5

O'xshashlar

TANLOV BO’YICHA SARALASH. ALGORITMNING MURAKKABLIGINI TAHLIL QILISH

TOPOLOGIK SARALASH. ALGORITMNING MURAKKABLIGINI BAHOLASH 2

Topologik saralash. Algoritmning murakkabligini baholash”

TOPOLOGIK SARALASH ALGORITMNING MURAKKABLIGINI BAHOLASH

MergeSort algoritmi.Algoritmning murakkabligini tahlil qilish