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

“Bo’lib tashla va hukmronlik qil” algoritmlari

Reja:

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

1. Bo’lib tashla va hukmronlik qil usuli
Bo’lib tashla va hukmronlik qil

"Dasturlashning eng asosiy muammosi — bu murakkablik. Murakkablikni hal qilishning faqatgina bitta asosiy yo'li bor: Bo'lib tashla va hukmronlik qil" — Bjarne Stroustrup
I qism. Bo'lib tashla va hukmronlik qil.
Oldingi bo'limlarimizda sizlar bilan eng fundamental algoritmlar va ma'lumotlar tuzilmalarini ko'rib chiqdik. Bu bo'limga kelib endi ancha jiddiy masalalar bilan shug'ullanishni boshlashimiz mumkin.
"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
  

Shu bilan bugungi "Bo'lib tashla va hukmronlik qil" bo'limiga kirish darsimizni nihoyasiga yetkazamiz va keyingi darslarda shu paradigma asosida ishlaydigan eng asosiy algoritmlarni ko'rib chiqamiz.

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.

Barcha turdagi bo’lib tashla va hukmronlik qil algoritmlari 3 ta bosqichdan iborat bo’ladi: