Laboratoriya ishi №1. Ma’lumotlarni saralash algoritmlarining murakkabligini tahlil qilish. Ustuvor navbatlar

Laboratoriya ishi №1. Ma’lumotlarni saralash algoritmlarining murakkabligini tahlil qilish. Ustuvor navbatlar.

Ishdan maqsad: Talabalarda algoritmlarni asimptotik tahlil qilish haqida ko’nikmalar hosil qilish, masalalarni yechishda saralash, qidirish algoritmlarini qo’llash va ularni tahlil qilish orqali qulayini tanlash.

Nazariy qism:

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.

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
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₂(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)

2. 
   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²)

3. 
   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)

4. 
   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⁵+n¹⁰) = O(n¹⁰)

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²) 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;
  
• 
  O(n*log(n)) – kvazichiziqli murakkablik;
  
• 
  O(2ⁿ) – eksponensial murakkablik;
  
• 
  O(n!) –factorial murakkablik.
  

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

Ustuvor navbatlarni 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.

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)

/* обработка ошибки - переполнение очереди */

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 (/ yoki sarlavha fayli) konstruksiyasi yordamida qilinadi.

class PriorityQueue {
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;
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)

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]);

down(0);

return a[size];

}
bool isEmpty() {

return size == 0;

}
};

Quyida mavjud algoritmlarning asimptotik tahlilini jadvallar bilan ko’rib chiqamiz. Bunda:

Yaxshi

Yomon__Yomon_holatda'>O’rta

Yomon

Saralash algoritmlari tahlili:

Algoritm__Ma’lumotlar_tuzilmasi__Vaqt_bo’yicha_murakkabligi'>Algoritm	Ma’lumotlar tuzilmasi	Vaqt bo’yicha murakkabligi				Qo’shimcha ma’lumotlar
		Yaxshi	O’rta	Yomon	Yomon holatda
Tezkor saralash	Massiv	O(n log(n))	O(n log(n))	O(n^2)	O(n)
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)

Qidirish algoritmlari tahlili:

Algoritm	Ma’lumotlar tuzilmasi	Vaqt bo’yicha murakkablik		Xotira bo’yicha murakkabligi
		O’rta	Yomon	Yomon
Chuqurlik bo’yicha qidirish (DFS)	|V| tepalik va |E| bog’lovchili graf	-	O(|E|+|V|)	O(|V|)
Kenglik bo’yicha qidirish (BFS)	|V| tepalik va |E| bog’lovchili graf	-	O(|E|+|V|)	O(|V|)
Binar qidirish	n elementdan iborat saralangan massiv	O(log(n))	O(log(n))	O(1)
Chiziqli qidirish	Massiv	O(n)	O(n)	O(1)
Deykstraning algoritmi bo’yicha ustuvor navbatlar (двоичная куча)dan foydalangan holda qisqa masofani toppish	|V| tepalik va |E| bog’lovchili graf	O((|V|+|E|)log|V|)	O((|V|+|E|)log|V|)	O(|V|)
Deykstraning algoritmi bo’yicha ustuvor navbatlar sifatida massivdan foydalangan holda qisqa masofani toppish	|V| tepalik va |E| bog’lovchili graf	O(|V|^2)	O(|V|^2)	O(|V|)
Bellman-Ford algoritmidan foydalangan holda qisqa masofani topish	|V| tepalik va |E| bog’lovchili graf	O(|V| |E|)	O(|V| |E|)	O(|V|)

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 elementlar bilan to’ldirilgan massiv	Surish Sheyker Tezkor	500	1600	5000
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.
  

Nazorat savollari:

1. 
   Nima sababdan algoritmlarning samaradorligini baholash amalga oshiriladi?
   
2. 
   Vaqt bo’yicha murakkablikda yaxshi va yomon holatlar bir xil bo’lishi mumkinmi? Xulosangizni misollar orqali tushuntiring.
   
3. 
   Rekursiv algoritmlarning murakabligini baholashning asosi nimada?
   
4. 
   Musbat butun son uchun faktorialni hisoblashning rekursiv va iteratsion usullarini vaqt bo’yicha murakkabligini baholang. Har bir holat uchun murakkablik sinfini aniqlang. Natijani tushuntiring.
   

Adabiyotlar ro’yhati:

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