ডিভাইড অ্যান্ড কঙ্কার৭ মিনিট পড়া

ডিভাইড অ্যান্ড কঙ্কার (D&C) প্যাটার্ন (Divide and Conquer Pattern)

সমস্যাটিকে ছোট ছোট টুকরাতে বিভক্ত করুন, টুকরোগুলোকে সমাধান করুন এবং তারপর সব ফলাফলগুলোকে একত্রিত করুন
template:T(n) = aT(n/b) + f(n)Master Thm:বেশিরভাগ D&C-এর রিকারেন্স (recurrence)-কে সহজেই সমাধান করে

ধরুন, আপনার ঘর একদম এলোমেলো অবস্থায় আছে। পুরো ঘর একা পরিষ্কার করার বিষয়টি আপনার কাছে বেশ অপ্রতিরোধ্য বা ওভারহোল্মিং (overwhelming) মনে হচ্ছে — ঠিক যতক্ষণ না পর্যন্ত আপনি বুঝতে পারলেন যে আপনি চাইলে কাজটিকে দুই ভাগে ভাগ করে নিতে পারেন। আপনি ঘরের একটা অর্ধেক পরিষ্কার করেন, আর আপনার ভাই বা বোন অপর অর্ধেকটা পরিষ্কার করে। আচমকা যেই কাজটি একটি বিশাল বড় কাজের মতো মনে হচ্ছিল, সেটি এখন মূলত দুটি ছোট কাজের মতো একই সময়ে হতে থাকছে। যখন আপনারা দুজনেই আপনাদের অর্ধেক ভাগগুলোর কাজ সম্পন্ন করে ফেলবেন, তখন ঠিক পুরো ঘরটি একসাথে পরিষ্কার হয়ে যাবে।

এই বিষয়টাই হলো ডিভাইড অ্যান্ড কঙ্কার (divide and conquer) (ভাগ করুন এবং জয় করুন)। যেকোনো কঠিন একটি সমস্যা (problem) নিন, সেটিকে ছোট ছোট টুকরোতে বা অংশে ভাঙুন, প্রতিটি টুকরোর স্বাধীনভাবে (independently) বা নিজে নিজে সমাধান করুন, এবং সবশেষে সেই ফলাফলগুলোকে একত্রিত করুন। এখানকার আসল ম্যাজিক বা জাদুটা হলো, অতি বিশাল পরিসরে কঠিন মনে হওয়া অনেক সমস্যাই (problems) খুব সহজ বা ট্রিভিয়ালি ইজি (trivially easy) হয়ে ওঠে যখন এর ইনপুটগুলো (input) যথেষ্ট ছোট আকারের হয়।

এর তিনটি প্রধান পর্যায় (The three phases)

ডিভাইড (Divide) বা বিভাজন: ইনপুটটিকে মূলত দুটি বা তার বেশি সংখ্যক ছোট ছোট সাব-প্রোব্লেমে (subproblem) বা উপ-সমস্যায় বিভক্ত করুন। এটি সাধারণত বলতে একটি সাধারণ অ্যারে-কে (array) দুই ভাগে ভাগ করা, এর সার্চ রেঞ্জ (search range) বা অনুসন্ধানের পরিসরকে সংকুচিত বা ন্যারো (narrowing) করা, অথবা কোনো পয়েন্টের বা বিন্দুর সেটকে (set) ভাগ করা বা পার্টিশনিং (partitioning) করাকে বোঝায়।

কঙ্কার (Conquer) বা জয়: প্রতিটি সাব-প্রোব্লেম বা উপ-সমস্যাকে রিকার্সিভলি (recursively) বা পুনরাবৃত্তিমূলকভাবে সমাধান করুন। এর বেস কেস (base case) বা মূল ভিত্তি হলো এমন একটি অবস্থা যখন উপসমস্যাটি এতটাই ছোট বা ক্ষুদ্র হয়ে যায় যে আপনি চাইলে সেটিকে সরাসরি সমাধান করে ফেলতে পারেন — যেমন ধরুন, উদাহরণস্বরূপ: 1 সাইজের বা ১ টি মাত্র উপাদান বিশিষ্ট একটি অ্যারে কিন্তু নিজে থেকেই ইতিমধ্যে সাজানো বা সর্টেড (sorted) থাকে।

কম্বাইন (Combine) বা একত্রীকরণ: তারপর সব উপসংহার বা সাব-সলিউশনগুলোকে (subsolutions) একত্রিত করে আসল সমস্যাটির বা অরিজিনাল প্রোব্লেমের (original problem) জন্য একটি পরিপূর্ণ সমাধানে পরিণত করুন। এটিই হলো সেই ধাপে যেখানে মূলত আসল ইন্টারেস্টিং বা আকর্ষণীয় কাজগুলো হয়ে থাকে — উদাহরণস্বরূপ: মার্জ সর্টে (merge sort) থাকা মার্জ (merge) ধাপের কথা বলা যেতে পারে।

কিছু ক্যানোনিকাল বা গতানুগতিক উদাহরণ (Canonical examples)

মার্জ সর্ট (Merge Sort): অ্যারেকে অর্ধেক করে বা দু'ভাগে বিভক্ত করে, প্রতিটি অর্ধাংশের আলাদাভাবে সর্ট বা সাজানো কাজ সম্পন্ন করা হয় এবং তারপর তাদেরকে মার্জ (merge) বা একত্রিত করে দেয়। যার একত্রীকরণ বা কম্বাইন (Combine) ধাপের খরচ হলো \(O(n)\)। রিকারেন্স (Recurrence): T(n) = 2T(n/2) + \(O(n)\) → \(O(n \log n)\)।

বাইনারি সার্চ (Binary Search): প্রতিটি ধাপে সার্চ স্পেস বা সন্ধানের পরিসরের (search space) পুরো অর্ধেক অংশকেই বাতিল করে দেয়। এর জন্য কোনো কম্বাইন (combine) বা একত্রিত করার ধাপের প্রয়োজন পড়ে না। রিকারেন্স (Recurrence): T(n) = T(n/2) + \(O(1)\) → \(O(\log n)\)।

স্ট্র্যাসেনের ম্যাট্রিক্স মাল্টিপ্লিকেশন বা গুণন (Strassen Matrix Multiplication): ম্যাট্রিক্সগুলোকে চারটি কোয়াড্রান্টে (quadrants) বিভক্ত করে এবং মোট ৮টির পরিবর্তে মূলত ৭টি রিকার্সিভ গুণন (recursive multiplications) ব্যবহার করে। রিকারেন্স (Recurrence): T(n) = 7T(n/2) + \(O(n^2)\) → \(O(n^{2.807})\)।

রিকারেন্স সেট আপ করা (Setting up the recurrence)

প্রতিটি ডিভাইড-অ্যান্ড-কঙ্কার (divide-and-conquer) নির্ভর অ্যালগরিদম ঠিক \(T(n) = a \cdot T(n/b) + f(n)\) এই ফর্ম বা নিয়মের মধ্যে ফিট (fit) হয়ে থাকে, যেখানে \(a\) হলো এর রিকার্সিভ কলগুলোর (recursive calls) সংখ্যা, \(b\) হলো ইনপুটগুলো (input) কল প্রতি ঠিক কতটা পরিমাণ হ্রাস পায় বা ছোট হয়, এবং \(f(n)\) হলো এর ডিভাইড বা বিভক্তকরণ এবং কম্বাইন বা একত্রীকরণের ধাপে ব্যয় হওয়া মূল খরচসমূহ। আর ঠিক এরপরেই মাস্টার থিওরেম (Master Theorem) মূলত \(f(n)\) এর সাথে \(n^{\log_b a}\) কে তুলনা করার মাধ্যমে এই সমস্যাটির সমাধান বের করে।

কখন D&C বা ডিভাইড-অ্যান্ড-কঙ্কার অন্যান্য উপায়গুলোকে ছাড়িয়ে যায় (When D&C beats other approaches)

আপনি ডিভাইড অ্যান্ড কঙ্কার (divide and conquer) এর পথে তখনই হাঁটবেন যখন সাব-প্রোব্লেমগুলো (subproblems) একে অপরের থেকে মূলত স্বাধীন (independent) (অর্থাৎ কোনো শেয়ারড স্টেট বা shared state নেই) হবে এবং এর কম্বাইন বা একত্রীকরণের (combine) ধাপ অনেকটাই সস্তা বা সলভেবল (solvable) হয়ে থাকে। আর যদি দুটি সাব-প্রোব্লেম ওভারল্যাপ (overlap) করে বা একে অপরের সাথে মিলে যায় — অর্থাৎ বারবার একই উত্তর বা সাব-অ্যানসারগুলো (sub-answers) কম্পিউট (compute) করতে থাকে — তাহলে আপনার উচিত ডায়নামিক প্রোগ্রামিং (dynamic programming)-এ সুইচ (switch) করা বা বদলানো। আর এর বদলে যদি কোনো সাধারণ গ্রিডি (greedy) পদ্ধতিটিই সবক্ষেত্রে ভালো কাজ করে যায়, তবে সেটিকে ঠিক তেমন সরল বা সিম্পল করেই রেখে দিন।

Click chart to zoom
ডিভাইড-অ্যান্ড-কঙ্কার বা D&C প্যাটার্নটি: এখানকার প্রতিটি কল হয় একটি ক্ষুদ্র বেস কেসের (base case) সরাসরি সমাধান করে, অথবা বিভক্ত (splits) হয়ে রিকার্স (recurses) করে তারপর তাকে একত্রিত (combines) করে।
দ্রষ্টব্য: এর সবচেয়ে গুরুত্বপূর্ণ বা মূল শব্দটি (key word) হলো 'স্বাধীন (independent)'। D&C তখনই সুন্দরভাবে কাজ করে বা পারফর্ম করে যখন একটি অর্ধাংশের (half) সমাধান অন্যটির ওপর নির্ভর করে না। আর ঠিক এই বিষয়টাই মূলত একে ডায়নামিক প্রোগ্রামিং (dynamic programming) থেকে আলাদা করে বা পৃথক করে, যেখানে সাব-প্রোব্লেম (subproblems) বা উপসমস্যাগুলো তাদের পূর্বের ফলাফলগুলো শেয়ার বা ভাগ করে নেয় এবং আপনাকে অবশ্যই সেগুলোকে সংরক্ষণ বা ক্যাশ (cache) করতে হয়।

মার্জ সর্ট (Merge Sort) — একটি ক্ল্যাসিক (Classic) ডিভাইড অ্যান্ড কঙ্কার

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # Conquer left
    right = merge_sort(arr[mid:])  # Conquer right
    return merge(left, right)      # Combine


def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]


arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))
Output
[3, 9, 10, 27, 38, 43, 82]

Complexity

✂️ ডিভাইড বা বিভাজন (Divide)
ইনডেক্স (index) দিয়ে একটি অ্যারেকে বিভক্ত করা হলো \(O(1)\); এবং অনুলিপি বা কপি (copying) করা হলো \(O(n)\)
সাধারণত লিনিয়ার (linear) বা ধ্রুবক (constant) \(O(1)\) – \(O(n)\)
🔁 কঙ্কার বা জয় করা (রিকার্স - recurse)
প্রতিটির সাইজ বা আকার \(n/b\) সমেত মূলত \(a\) সংখ্যক উপসমস্যা বা সাব-প্রোব্লেমগুলো (subproblems)
ব্রাঞ্চিংয়ের বা শাখার বিস্তৃতির ওপর নির্ভর করে (Depends on branching) \(a \cdot T(n/b)\)
🔗 কম্বাইন বা একত্রীকরণ (Combine)
মার্জ সর্ট (Merge sort): \(O(n)\); বাইনারি সার্চ (binary search): \(O(1)\)
অ্যালগরিদম অনুসারে ভিন্ন হয় (Varies by algorithm) \(f(n)\)
📘 মাস্টার থিওরেম-এর ১ম কেস (Master Theorem Case 1)
যখন \(f(n) = O(n^{\log_b(a) - \epsilon})\) হয়
সাব-প্রোব্লেমগুলোই (Subproblems) আধিপত্য বিস্তার করে বা ডমিনেট করে \(O(n^{\log_b(a)})\)
📗 মাস্টার থিওরেম-এর ২য় কেস (Master Theorem Case 2)
যখন \(f(n) = \Theta(n^{\log_b(a)})\) হয় — মার্জ সর্ট বা merge sort ঠিক এই অংশে বা কেসে পড়ে
ব্যালেন্সড বা সুষম (Balanced) — সমানভাবে বিভক্ত (evenly split) \(O(n^{\log_b(a)} \cdot \log n)\)
📕 মাস্টার থিওরেম-এর ৩য় কেস (Master Theorem Case 3)
যখন \(f(n) = \Omega(n^{\log_b(a) + \epsilon})\) হয়
কম্বাইন বা একত্রিত (combine) করার ধাপটি আধিপত্য বা ডমিনেট করে \(O(f(n))\)

ছোট কুইজ

মার্জ সর্ট (Merge Sort) এর রিকারেন্স (recurrence) হলো \(T(n) = 2T(n/2) + O(n)\)। এটি মূলত মাস্টার থিওরেমের (Master Theorem) কোন কেসটিতে প্রযোজ্য হবে?

পড়া চালিয়ে যান

মার্জ সর্ট (Merge Sort)
ভাগ করুন, প্রতি অর্ধেক সাজান, তারপর একত্রিত (merge) করুন — প্রতিবারই \(O(n \log n)\) এর নিশ্চয়তা
→
রিকারেন্স রিলেশন (Recurrence Relations)
নিজে নিজেকে ডাকা একটি রেসিপি — সমাধান করতে পারার মতো সহজ না হওয়া পর্যন্ত
→
ইনভার্সন গণনা (Count Inversions)
একটি সিকোয়েন্স (sequence) বা ক্রম ঠিক কতটা এলোমেলো অবস্থায় আছে তা পরিমাপ করুন — \(O(n \log n)\) সময়ে
→