რა არის divide-and-conquer პარადიგმა?

Question

Accepted Answer

**Divide and conquer** წყვილ-დაპყრობის პრინციპი აგვარებს პრობლემას (1) მის **დაყოფით** უფრო პატარა ქვე-პრობლემებად, (2) თითოეულის **დაპყრობით** რეკურსიულად, და (3) შედეგების **გაერთიანებით**. ბევრი ეფექტური ალგორითმი ამ შაბლონს მიჰყვება.

## იდეა

თუ ქვე-პრობლემები დამოუკიდებელი არიან და სწრაფად იკლებენ, მთლიანი სამუშაო დაიმორჩილებს რეკურენტულ ურთიერთობას, რომელიც შეგიძლიათ გაანალიზოთ **Master Theorem**-ის საშუალებით.

## მაგალითი: მაქსიმალური ელემენტი divide and conquer-ის მეშვეობით

```python
def max_dc(arr, lo, hi):
    if lo == hi:                       # base case: one element
        return arr[lo]
    mid = (lo + hi) // 2
    left = max_dc(arr, lo, mid)        # conquer left
    right = max_dc(arr, mid + 1, hi)   # conquer right
    return max(left, right)            # combine

max_dc([3, 9, 2, 7], 0, 3)            # -> 9
```

## კლასიკური მაგალითები

- **Merge sort / quicksort** — O(n log n) დალაგება.
- **Binary search** — O(log n).
- **Fast exponentiation, Karatsuba multiplication, closest pair.**

## სირთულე

ხშირად T(n) = a·T(n/b) + f(n); merge sort-ის შემთხვევაში, T(n) = 2T(n/2) + O(n) = **O(n log n)**.

## როდის გამოვიყენოთ / პასტები

გამოიყენეთ მაშინ, როდესაც პრობლემა **깔끔하게 იყოფა** დამოუკიდებელ ქვე-პრობლემებად. თუ ქვე-პრობლემები **გადაკვეთილია**, მიმართეთ დინამიკური პროგრამირების გამოყენებას (გადამუშავების თავიდან აცილებისთვის). რეკურსიის ზეგვირგვინი და გაერთიანების ეტაპი შეიძლება დომინირებდეს მცირე შეყვანილებებისთვის.

## რატომ მნიშვნელოვანია

Divide and conquer არის გამოყენებადი ნიმუში, რომელიც დევს ეფექტური ალგორითმების დიდი ნაწილის უკან.

ამ ნიმუშის ცნობა გიძლევთ ახალი ალგორითმების წარმოშობისა და გაანალიზების სწრაფად განხორციელების საშუალებას რეკურენტული ურთიერთობის გამოყენებით.

ის ასევე ბუნებრივად აკარტოვებს პარალელიზმზე, რადგან დამოუკიდებელი ქვე-პრობლემები შეიძლება მუშაობდეს ერთდროულად.