Divide and Conquer Algorithm

Bo'lib tashla va hukmronlik qil (Divide and Conquer) algoritmi — bu katta muammoni quyidagi tartibda hal qilish strategiyasidir:

1. Muammoni kichikroq quyi muammolarga (sub-problems) bo'lish
2. Quyi muammolarni yechish
3. Kerakli natijani olish uchun ularni birlashtirish.

Bo'lib tashla va hukmronlik qil algoritmidan foydalanish uchun rekursiya (recursion) ishlatiladi.

Bo'lib tashla va hukmronlik qil algoritmlari qanday ishlaydi?

Bu quyidagi qadamlarni o'z ichiga oladi:

1. Bo'lish (Divide): Berilgan muammoni rekursiya yordamida kichikroq quyi muammolarga bo'lish.
2. Hukmronlik qilish (Conquer): Kichikroq quyi muammolarni rekursiv ravishda yechish. Agar quyi muammo yetarlicha kichik bo'lsa, uni to'g'ridan-to'g'ri yechish.
3. Birlashtirish (Combine): Haqiqiy muammoni hal qilish uchun rekursiv jarayonning bir qismi bo'lgan quyi muammolar yechimlarini birlashtirish.

Keling, ushbu tushunchani bitta misol orqali tushunib olaylik. Bu yerda biz massivni bo'lib tashla va hukmronlik qil yondashuvi yordamida saralaymiz (ya'ni Merge Sort).

1. Berilgan massiv quyidagicha bo'lsin:

2. Massivni ikkita yarimga bo'lamiz:

Yana, yakka elementlar hosil bo'lguniga qadar har bir qismni rekursiv ravishda ikkiga bo'lishda davom etamiz:

3. Endi yakka elementlarni saralangan tartibda birlashtiramiz. Bu yerda yechish (conquer) va birlashtirish (combine) qadamlari yonma-yon boradi:

Vaqt murakkabligi

Bo'lib tashla va hukmronlik qil algoritmining murakkabligi Master teoremasi yordamida hisoblanadi.

T(n) = aT(n/b) + f(n)

Bu yerda:

• n = kiruvchi ma'lumotlar hajmi
• a = rekursiyadagi quyi muammolar soni
• n/b = har bir quyi muammoning hajmi. Barcha quyi muammolar bir xil hajmga ega deb hisoblanadi.
• f(n) = rekursiv chaqiruvdan tashqarida bajarilgan ishlar xarajati, bu muammoni bo'lish xarajati va yechimlarni birlashtirish xarajatini o'z ichiga oladi.

Rekursiv muammoning vaqt murakkabligini topish uchun bitta misol ko'raylik. Merge sort uchun tenglama quyidagicha yozilishi mumkin:

T(n) = aT(n/b) + f(n)
     = 2T(n/2) + O(n)

Bu yerda:

• a = 2 (har safar muammo 2 ta quyi muammoga bo'linadi)
• n/b = n/2 (har bir quyi muammoning hajmi kiruvchi ma'lumotning yarmiga teng)
• f(n) = muammoni bo'lish va quyi muammolarni birlashtirish uchun ketgan vaqt
• T(n/2) = O(n log n) (Buni tushunish uchun Master teoremasiga qarang.)

Endi:

T(n) = 2T(n log n) + O(n)
     ≈ O(n log n)

Bo'lib tashla va hukmronlik qil vs Dinamik yondashuv

Bo'lib tashla va hukmronlik qil yondashuvi muammoni kichikroq quyi muammolarga ajratadi; bu quyi muammolar keyinchalik rekursiv ravishda yechiladi. Har bir quyi muammoning natijasi kelajakda foydalanish uchun xotirada saqlanmaydi. Dinamik yondashuvda esa har bir quyi muammoning natijasi kelajakda foydalanish uchun saqlab boriladi.

Bir xil quyi muammo bir necha marta qayta yechilmaydigan holatlarda bo'lib tashla va hukmronlik qil yondashuvidan foydalaning. Quyi muammoning natijasi kelajakda ko'p marta ishlatiladigan holatlarda esa dinamik yondashuvdan foydalaning.

Keling, buni bitta misol orqali tushunib olaylik. Faraz qilaylik, biz Fibonachchi ketma-ketligini topmoqchimiz. Unda:

Divide and Conquer yondashuvi:

fib(n)
    agar n < 2 bo'lsa, 1 qaytarish
    aks holda, f(n - 1) + f(n - 2) qaytarish

Dinamik yondashuv:

mem = []
fib(n)
    agar n mem ichida mavjud bo'lsa: mem[n] ni qaytarish
    aks holda:
        agar n < 2 bo'lsa, f = 1
        aks holda, f = f(n - 1) + f(n - 2)
    mem[n] = f
    f ni qaytarish

Dinamik yondashuvda mem har bir quyi muammoning natijasini saqlaydi.

Bo'lib tashla va hukmronlik qil algoritmining afzalliklari

• Ikkita matritsani oddiy usulda ko'paytirish murakkabligi O(n³) bo'lsa, bo'lib tashla va hukmronlik qil yondashuvi (ya'ni Shtrassen matritsalarni ko'paytirish usuli) orqali bu O(n^2.8074) ga tushadi. Bu yondashuv Xanoy minorasi kabi boshqa masalalarni ham soddalashtiradi.
• Ushbu yondashuv ko'p protsessorli (multiprocessing) tizimlar uchun mos keladi.
• U kesh xotiradan samarali foydalanadi.

Bo'lib tashla va hukmronlik qil tatbiqlari

• Binary Search
• Merge Sort
• Quick Sort
• Strassen's Matrix multiplication
• Karatsuba Algorithm