Farg‘ona davlat universiteti

Bo’lib tashla va hukmronlik qil paradigmasi asosiy masalalari

Bu paradigma dasturlashning juda mashhur algoritmlari asosini tashkil qiladi:

1. 
   Ikkilik qidirish (Binary Search)
   
2. 
   Merge Sort
   
3. 
   Quick Sort
   
4. 
   Eng yaqin ikki nuqta (Closest two points)
   
5. 
   Strassen ko’paytirishi (Strassen multiplication)
   
6. 
   Karatsuba algoritmi (Karatsuba algorithm)
   
7. 
   Cooley-Tukey algoritmi (Cooley-Tukey Algorithm)
   

Stek
Stekning implementasiyasi ikki xil usulda bajarilishi mumkin. Zanjir(Linked) va Massiv.


Zanjir yoki Linked Stek.  Stekdagi barcha element o’zidan keyingi elementga bo’glangan bo’ladi va ushbu ketma-ketlik yordamida stekdagi “top” elementni aniqlab olamiz. Ushbu usulda yaratilga Stekning vaqt murakkabligi quyidagi jadvalda berilgan.

Amal	Murakkablik
Push(T value)	\(O(1)\)
Pop()	\(O(1)\)
Peek()	\(O(1)\)
IsEmpty()	\(O(1)\)
Size()	\(O(1)\)

Barcha amallarni asosini o’zlashtirish amali tashkil qilgani sababi barcha metodlar \(O(1)\) vaqtda bajariladi.
Massivga asoslangan Stek. Massivning qulayliklaridan biri bu indeks orqali massivda joylashgan elementni vaqtda qaytara olishdir. Lekin massivdagi elementlar soni ko’payib ketsa qimmatbaho amal – hajmni kengaytirish lozim bo’ladi. O’z hajmini o’zi o’zgartira oladigan massiv dinamik massiv deyiladi.

Amal	Murakkablik
Push(T value)	Resize()ga qarang.
Pop()	\(O(1)\)
Peek()	\(O(1)\)
IsEmpty()	\(O(1)\)
Size()	\(O(1)\)
Resize()	Eng yomon holatda \(O(n)\), o’rtacha esa \(O(1)\) vaqt oladi.

"Bo'lib tashla va hukmronlik qil" usulining eng mashhur saralash algoritmlaridan biri Merge Sort (Birlashtirib saralash)dir. Merge Sort algoritmi
Nazariyaga ko’ra Push(T value) O(n) bu eng yomon holatdur, lekin Resize()ning chaqirilish ehtimolligi har chaqirilgandan so’ng pasayib boradi. Natijada, yuqoridagi metodni vaqt murakkablikka ega deb qabul qilishimiz mumkin.
Merge Sort va uning ishlash prinsipi
Merge Sort bu saralanmagan arrayni taqqoslashga asoslangan holda saralovchi algoritm bo’lib, uning ishlash prinsipi “Bo’lib tashla va hukmronlik qil” paradigmasi asosiga qurilgan

"Bo'lib tashla va hukmronlik qil" usulining eng mashhur saralash algoritmlaridan biri Merge Sort (Birlashtirib saralash)dir.Merge Sort algoritmi bu saralanmagan massivni taqqoslashga asoslangan holda saralovchi algoritm bo'lib, uning ishlash printsipida to'liq bo'lib tashla va hukmronlik qil g'oyasini uchratish mumkin. Demak, merge sort algoritmi asosiy ikkita qismdan iborat:

1. 
   Berilgan massivni rekursiv holda teng ikkita qismlarga bo'lib chiqish. Bu qadam, qism massivlar uzunligi 1 ga (yoki undan kichik) teng bo'lib qolguncha davom etadi.
   
2. 
   Hosil bo'lgan massivlarni qaytib birlashtirib chiqish va bir vaqtning o'zida hosil bo'luvchi massiv saralangan bo'lishini ta'minlash.
   

Merge sort algoritmi qanday ishlashini vizual tasavvur qilish uchun quyidagi rasmga e'tibor bering. Unda amallar tartibi ham ko'rsatib qo'yilgan(6.3-rasm).
Ko'rib turganingizdek algoritm ishlash prinsipini tushunish uchun unchalik ham murakkab emas. Va yana e'tibor bergan bo'lsangiz, birinchi bo'linishdan keyingi massivning chap va o'ng qismlarida asosiy massiv bilan bir xil amal ketmoqda, ya'ni bizning masalamizning qism masalasi ham bosh masala bilan bir xilda ishlaydi.
Merge sort algoritmi qadamlari:

1. 
   Merge Sort funksiyasiga massiv va uning boshlang'ich (left) va oxirgi nuqtalari (right) beriladi.
   
2. 
   Massivning o'rtasi hisoblanadi: mid = (left + right)/2. Bu uni teng ikkiga bo'lish uchun kerak bo'ladi.
   
3. 
   Merge sortni rekursiv holda birinchi va ikkinchi qismlar uchun chaqiriladi.
   
4. 
   2- va 3-qismlarda hosil bo'lgan massivlar birlashtirib chiqiladi. (Massiv mavzusidagi ikkita massivni birlashtirish masalasini ko'rib chiqing)
   

Algoritm ishlash tezligiO(nlogn)bo'lib tezligi O(n²) bo'lgan oddiy Bubble,Insertion, Selection Sortlardan ancha tez ishlaydi. O'zi umuman olganda, taqqoslashasosidaishlaydiganalgortmlarningengtezishlashholatiO(nlogn)bo'lishiisbotlangan.Merge sort turg'un saralash hisoblanadi, ya'ni saralamagan massivda bir nechta bir xil elementlar kelgan bo'lsa, ularning tartibi saralangan massivda ham o'zgarib ketib qolmaydi.Algoritm ishlashi uchun xotiradan qo'shimcha O(n) joy talab qiladi.Bo'lib tashla va hukmronlik qil paradigmasi asosida ishlaydigan eng mashhur algoritm — bu ikkilik qidirish (binary search).Ikkilik qidirish algoritmi saralangan massivdan element topishning eng samarali algoritmlaridan biri.

3-rasm. Merge sort algoritmining ishlash printsipi.


Merge sort qanday ishlashini vizual tasavvur qilish uchun quyidagi ajoyib animatsiyani ko’rishingiz mumkin.


Image source: Gfycat
Bu animatsiyadan algoritm realizatsiyasini to’liq tasavvur qilish qiyin bo’lishi mumkin. Shuning uchun quyidagi rasmni ham keltirib o’tamiz. U yerda algoritm qanday ishlashi qadamma-qadam ko’rsatilgan:


Image source: Baeldung
Ko’rib turganingizdek algoritm ishlash prinsipini tushunish uchun unchalik ham murakkab emas. Va yana e’tibor bergan bo’lsangiz, birinchi bo’linishdan keyingi arrayning chap va o’ng qismlarida asosiy array bilan bir xil amal ketmoqda, ya’ni bizning masalamizning qism masalasi ham bosh masala bilan bir xilda ishlaydi.
Endi esa algoritmni implementatsiya qilish uchun qadamma-qadam nima qilish kerakligiga o’tamiz