Bo’lib tashla va hukmronlik qil usuli. Kesh xotira bilan ishlash. Qo’llanish muammolari

Bo’lib tashlash 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.
Shu sababli, bo’lib tashla hukmronlik qil paradigmasini 3 ta jumla bilan eslab qolish mumkin: 


bo’lib tashla

hukmronlik qil

birlashtir

Bo’lib tashla va hukmronlik qil paradigmasi dasturlashning mashhur algoritmlari asosini tashkil qiladi:

• 
  Quick Sort
  

• 
  Merge Sort
  

• 
  Eng yaqin ikki nuqta (Closest two points)
  

• 
  Strassen ko’paytirishi (Strassen multiplication)
  

• 
  Karatsuba algoritmi (Karatsuba algorithm)
  

• 
  Cooley-Tukey algoritmi (Cooley-Tukey Algorithm)
  

• 
  qiyin masalalarni osonlik bilan yechishga imkon beradi
  

Bo’lib tashla va hukmronlik qil paradigmasining afzalliklari

• 
  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)