Ajrat va hukmronlik qil tilidagi algoritmlar reja

1-rasm. Bir qadamdan iborat “ajrat va hukmronlik qil” algoritmining ishlash printsipi.

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

• 
  Agar biz qadamlar sonini oshiradigan bo’lsak, paradigma tasviri quyidagicha ko’rinish oladi
  

2- rasm. Ko’p qadamdan iborat “ajrat va hukmronlik qil” algoritmining ishlash printsipi

Ajrat va hukmronlik qil paradigmasi asosiy masalalari

• 
  Bu paradigma dasturlashning juda mashhur algoritmlari asosini tashkil qiladi:
  
• 
  Ikkilik qidirish (Binary Search)
  
• 
  Merge Sort
  
• 
  Quick Sort
  
• 
  Eng yaqin ikki nuqta (Closest two points)
  
• 
  Strassen ko’paytirishi (Strassen multiplication)
  
• 
  Karatsuba algoritmi (Karatsuba algorithm)
  
• 
  Cooley-Tukey algoritmi (Cooley-Tukey Algorithm)
  

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

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