divide-and-conquer paradigm क्या है?

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)।
- **तेजी से घातांक, Karatsuba गुणन, निकटतम जोड़ी।**

## जटिलता

अक्सर T(n) = a·T(n/b) + f(n); merge sort के लिए, T(n) = 2T(n/2) + O(n) = **O(n log n)**।

## कब उपयोग करें / नुकसान

जब एक समस्या स्वतंत्र उप-समस्याओं में **स्पष्ट रूप से विभाजित** हो तो उपयोग करें। यदि उप-समस्याएं **ओवरलैप** करती हैं, तो पुनर्गणना से बचने के लिए गतिशील प्रोग्रामिंग को प्राथमिकता दें। पुनरावर्तन ओवरहेड और संयोजन चरण छोटे इनपुट के लिए प्रभावशाली हो सकते हैं।

## यह क्यों महत्वपूर्ण है

Divide and conquer कुशल एल्गोरिदम के विशाल अंश के पीछे एक पुन: प्रयोज्य ब्लूप्रिंट है।

पैटर्न को पहचानना आपको पुनरावर्तन के साथ जल्दी नए एल्गोरिदम प्राप्त और विश्लेषण करने देता है।

यह स्वाभाविक रूप से समानांतरता तक मैप करता है, क्योंकि स्वतंत्र उप-समस्याएं समवर्ती रूप से चल सकती हैं।