Ajrat va hukmronlik qil

“Ajrat va hukmronlik qil”algoritmi

Dasturlashda, ajrat va hukmronlik qil — bu algoritmik paradigm  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. Barcha turdagi bo’lib tashla va hukmronlik qil algoritmlari 3 ta bosqichdan iborat bo’ladi:

• 
  Dasturlashda, ajrat va hukmronlik qil — bu algoritmik paradigm  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. Barcha turdagi bo’lib tashla va hukmronlik qil algoritmlari 3 ta bosqichdan iborat bo’ladi:
  
• 
  Ajrat bosqichi. Bunda bosh masala huddi shu masalaga o’xshash kichikroq masalalarga bo’lib chiqiladi.
  
• 
  Hukmronlik bosqichi. Asos holatimizga mos kelib qolgan qism masalalar huddi u kabi yechiladi.
  
• 
  Birlashtirish bosqichi. Bu bosqichda yechilgan kichik qism masalalar qaytib birlashtirib chiqiladi va bu bosh masala yechimi bo’ladi.
  

Shuning uchun, bo'lin va hukmronlik paradigmasini 3 ta jumla bilan eslash mumkin: bo'lish , hukmronlik qilish , birlashtirish . Keling, oddiy, bir bosqichli bo‘lish va zabt etish algoritmi qanday ishlashini ko‘rib chiqamiz (1-rasm):

• 
  Shuning uchun bo'l va hukmronlik paradigmasini 3 ta jumla bilan eslab qolish mumkin: bo'lish , hukmronlik qilish, birlashtirish . Keling, oddiy, bir bosqichli bo‘lish va zabt etish algoritmi qanday ishlashini ko‘rib chiqamiz
  

Ajrat va hukmronlik qil paradigmasi kamchiliklari

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

Ikkilik qidirish algoritmining ishlash prinsipi

• 
  Ikkilik qidirish algoritmini ishlash prinsipini tushunish uchun keling kompyuter bilan o'yin o'ynab ko'ramiz. O'yin shartlari quyidagicha:
  
• 
  Kompyuter 1 dan 100 gacha ixtiyoriy son tanlaydi. Sizning vazifangiz shu sonni iloji boricha kam taxmin ishlatgan holda topish.
  
• 
  Har bir taxmindan keyin kompyuter sizga sizning taxminingiz kompyuter o'ylagan sondan katta yoki kichikligini aytadi.
  
• 
  Agar sizning taxminingiz kompyuter o'ylagan son bilan bir xil bo'lsa, o'yin tugaydi.
  
• 
  Xo'sh, bunda kamroq yo'l tutish uchun nima qilgan bo'lar edingiz?
  
• 
  Aytaylik kompyuter bizga taxminimiz o'ylangan sondan kichikroq ekanligini aytdi. Demak, endi biz 50 va undan kichik barcha son o'ylangan sondan kichik ekanligini bilamiz. Shunday qilib, bizning qidirish sohamiz ikki baravarga qisqaradi (50 ta son). Huddi shu tarzda davom etamiz. Endi 51 dan 100 gacha sonlar o'rtasidagi sonni olamiz, ya'ni 75 ni.
  

• 
  Aytaylik kompyuter bizga taxminimiz o'ylangan sondan kichikroq ekanligini aytdi. Demak, endi biz 50 va undan kichik barcha son o'ylangan sondan kichik ekanligini bilamiz. Shunday qilib, bizning qidirish sohamiz ikki baravarga qisqaradi (50 ta son). Huddi shu tarzda davom etamiz. Endi 51 dan 100 gacha sonlar o'rtasidagi sonni olamiz, ya'ni 75 ni.
  
• 
  Sonlar 100 ta bo'lgan holatda, biz har qanday tahminni ko'pi bilan 7 ta qadamda topishimiz mumkin bo'ladi. Ikkilik qidirish algoritmi ham huddi shunday prinsipda ishlaydi!
  
• 
  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
  
• 
  Avvaliga l = 0 va r=n-1 bo'ladi (butun boshli massiv)
  
• 
  O'rtadagi element indeksi hisoblanadi: mid = (l + r)/2;
  
• 
  O'rtadagi element indeksi bilan qidirilayotgan son x solishtirib ko'riladi
  
• 
  Agar son mos kelsa, algoritm shu joyida to'xtaydi.
  
• 
  Agar x o'rtadagi sondan katta bo'lsa, left ko'rsatkichni o'rtadan bitta keyingi elementga suramiz: l=mid + 1;
  
• 
  Agar x o'rtadagi sondan kichik bo'lsa, right ko'rsatkichni o'rtadan bitta oldingi elementga suramiz: r=mid — 1;
  
• 
  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.