Bo’lib tashla va hukmronlik qil

Algoritm qadamlari

Ikkilik qidirish algoritmi to'g'ri ishlashi uchun massiv saralangan bo'lishi shart! Bizda n ta elementli saralangan massiv bor va biz undan x elementni qidirmoqdamiz. Biz qidirish chegarasini belgilash uchun l (left) va r (right) ko'rsatkichlardan foydalanamiz. Ular massiv indekslarini ko'rsatib turadi. mid o'zgaruvchi bizda qidirilayotgan sohaning o'rtadagi elementi indeksini ko'rsatadi
1. Avvaliga l = 0 va r=n-1 bo'ladi (butun boshli massiv)
2. O'rtadagi element indeksi hisoblanadi: mid = (l + r)/2;
3. O'rtadagi element indeksi bilan qidirilayotgan son x solishtirib ko'riladi
4. Agar son mos kelsa, algoritm shu joyida to'xtaydi.
5. Agar x o'rtadagi sondan katta bo'lsa, left ko'rsatkichni o'rtadan bitta keyingi elementga suramiz: l=mid + 1;
6. Agar x o'rtadagi sondan kichik bo'lsa, right ko'rsatkichni o'rtadan bitta oldingi elementga suramiz: r=mid — 1;
7. 2-qadamga qaytiladi.
Ikkilik qidirish algoritmi har bir qadamda n ni ikki baravarga kamaytirgani uchun algoritm ishlash tezligi O(logn) hisoblanadi. Solishtirish uchun Facebook misolidagi 1 mlrd login ichidan ikkilik qidirish algoritmi 30 ta (!) qadam bilan topishi mumkin. Oddiy qidirishdan tashqari bu algoritmni yana boshqa juda ko'p joyda qo'llash mumkin.
Nazorat savollari
1. “Bo’lib tashla va hukmronlik qil” algoritmining bosqichlarini ayting.
2. Qanday saralash algoritmlarini bilasiz?
3. Saralash algoritmlari samaradorligini qanday baholash mumkin?
4. Stek tuzilmasini tushuntiring va misol keltiring.
5. Binar daraxtiga yangi element qo‟shish algoritmini tushuntiring.
6. Quicksort algoritmini tushuntiring.


Adabiyotlar
1. Кленберг Дж.,Тардос Е.”Алгоритмы.Разработка и применение”.2016г.
2. Кормен Т.,Лейзерсон Ч.,Ривест Р.«Алгоритмы.Построение и анализ»,2013г.
3. Колдаев. Основы_алгоритмизации_и программирования. 2013 г.


4. Г.Уоррен «Алгоритмические трюки для программистов», 2014 г.
"Bo'lib tashla va hukmronlik qil" nimani anglatadi
Dasturlashda, bo'lib tashla va hukmronlik qil — bu algoritmik paradigma bo'lib, bu paradigmaning asosiy g'oyasi algoritmik masalalarni bosh masalaga o'xshash kichik qismlarga bo'lib tashlab, ularni rekursiv hal qilishdan iborat.
Bu paradigmada masala qismlarga bo'linganligi sababli, qism masalalar bosh masalaga qaraganda kichikroq bo'lishi va bu bo'linish to'xtashi uchun asos holat bo'lishi kerak (Rekursiya esingizga tushib ketmadimi?). Barcha turdagi bo'lib tashla va hukmronlik qil algoritmlari 3 ta bosqichdan iborat bo'ladi:

1. 
   Bo'lib tashlash bosqichi. Bunda bosh masala huddi shu masalaga o'xshash kichikroq masalalarga bo'lib chiqiladi.
   
2. 
   Hukmronlik bosqichi. Asos holatimizga mos kelib qolgan qism masalalar huddi u kabi yechiladi.
   
3. 
   Birlashtirish bosqichi. Bu bosqichda yechilgan kichik qism masalalar qaytib birlashtirib chiqiladi va bu bosh masala yechimi bo'ladi.
   

Shu sababli, bo'lib tashla hukmronlik qil paradigmasini 3 ta jumla bilan eslab qolish mumkin: bo'lib tashla, hukmronlik qil, birlashtir. Boshida tushunish ozroq qiyin bo'lishi tabiiy, shuning uchun bu paradigma g'oyasini tasvirlab berishga harakat qilamiz.
Oddiy, bittagina qadamdan iborat bo'lib tashla va hukmronlik qil algoritmi qanday ishlashini ko'raylik:

Agar biz qadamlar sonini oshiradigan bo'lsak, paradigma tasviri quyidagicha ko'rinish oladi:

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)
   

Bulardan eng asosiylarini keyingi darslarimizda ko'rib chiqamiz
Bo'lib tashla va hukmronlik qil paradigmasi afzalliklari

• 
  qiyin masalalarni osonlik bilan yechishga imkon beradi
  
• 
  bu paradigmaga asoslangan algoritmlar oddiy yechimlardan ko'ra tezroq ishlaydi. Masalan: oddiy saralash bo'lgan Bubble Sortning tezligi O(n²) bo'lsa, MergeSortniki O(n*logn)
  
• 
  bunday algoritmlarni parallel hisoblovchi sistemalarda hech qanday o'zgarishsiz ishlatish mumkin
  
• 
  bunday algoritmlarni qo'llashda xotira keshidan unumli foydalanish mumkin. Chunki masalalar bo'linish jarayonida shunday kichik qismlarga ajraladiki, ularni keshni o'zida turib yechish mumkin bo'ladi.
  
• 
  haqiqiy sonlar uchun bunday algoritmlar aniqroq ishlaydi, chunki qism yechimlardagi haqiqiy sonlar ustidagi amallar aniqroq bajariladi (masalan, ko'paytirish algoritmlarida)
  

Bo'lib tashla va hukmronlik qil paradigmasi kamchiliklari

• 
  bunday paradigma asosida ishlaydigan algoritmlar rekursiyadan foydalanadi va bu narsa ularni ishlashini ma'lum miqdorga sekinlashtiradi. Buning ustiga kichik bir xato yechimni cheksiz takrorlanishga tushirib qo'yishi mumkin.
  
• 
  asos shartni tanlashda yo'l qo'yilgan xato barcha qism masalalarda xatolik va ortiqcha xotira ishlatilishiga olib keladi