ডিভাইড অ্যান্ড কনকার প্যারাডাইম

১ · তিনটি ধাপ — ডিভাইড, কনকার, কমবাইন

ডিভাইড অ্যান্ড কনকারDivide and Conquerএকটি ডিজাইন প্যারাডাইম যেখানে একটি সমস্যাকে ছোট, একই ধরনের সাব-প্রবলেমে ভাগ করা হয়, প্রতিটি রিকার্সিভভাবে সমাধান করা হয়, এবং সাব-সমাধানগুলো জোড়া দিয়ে মূল সমাধান তৈরি করা হয়। হলো একটি সাধারণ, বহু অ্যালগরিদমে পুনরাবৃত্ত হওয়া টেমপ্লেট। এর তিনটি ধাপ:

সাধারণ সিউডোকোড আকারে লিখলে:

function solve(problem):
    if problem is small enough (base case):
        return direct_solution(problem)
    subproblems = divide(problem)          # ডিভাইড
    sub_solutions = [solve(sp) for sp in subproblems]   # কনকার (রিকার্সিভ কল)
    return combine(sub_solutions)          # কমবাইন

২ · পরিচিত D&C অ্যালগরিদম — ../dsa/ কোর্সে যা দেখেছেন

নিচের তিনটি অ্যালগরিদমের ইমপ্লিমেন্টেশন ও মেকানিক্স ইতিমধ্যে DSA কোর্সে কভার করা হয়েছে — এখানে শুধু D&C টেমপ্লেটের সাথে কীভাবে মেলে তা দেখা হচ্ছে; L15–L18-এ প্রতিটির রিগোরাস রানটাইম-অ্যানালাইসিস আসবে।

লক্ষ্য করুন — কমবাইন ধাপের খরচ প্রতিটিতে ভিন্ন: মার্জ সর্টে $O(n)$ (মার্জ করতে পুরো অ্যারে ঘুরতে হয়), কুইক সর্ট ও বাইনারি সার্চে $O(1)$ (কিছুই করার নেই)। এই পার্থক্যই মূলত তাদের রানটাইম রিকারেন্সের $f(n)$ অংশ নির্ধারণ করে।

৩ · রানটাইম একটি রিকারেন্স হিসেবে

যেকোনো D&C অ্যালগরিদমের রানটাইম সাধারণভাবে এভাবে লেখা যায়:

এখানে $a$ = কতগুলো সাব-প্রবলেম তৈরি হয় (কনকার ধাপে কতবার রিকার্সিভ কল হয়), $b$ = প্রতিটি সাব-প্রবলেমের আকার মূল সমস্যার তুলনায় কত ভাগের এক ভাগ (ডিভাইড ফ্যাক্টর), এবং $f(n)$ = ডিভাইড ও কমবাইন ধাপের নিজস্ব খরচ (রিকার্সিভ কলগুলো বাদে)। এটি ঠিক সেই ফর্ম যা M3-এ (L10–L13) সাবস্টিটিউশন মেথড, রিকার্সন ট্রি মেথড এবং মাস্টার থিওরেম দিয়ে সমাধান করার কৌশল শেখা হয়েছে — এই মডিউল সেই টুলগুলো সরাসরি প্রয়োগ করবে:

৪ · কম্পিউটেশনাল ডেমো — রিকার্সিভ স্প্লিটিং প্যাটার্নের আকার

L15–L18-এ আমরা প্রতিটি অ্যালগরিদমের তুলনার সংখ্যা গুনব। এখানে, তার আগে, শুধু D&C-এর রিকার্সিভ কল-স্ট্রাকচারটাই কেমন দেখতে — সেটা সরাসরি গুনে দেখি। নিচের কোডে একটি অ্যারের সর্বোচ্চ মান বের করার একটি (ইচ্ছাকৃতভাবে সরল, অপটিমাইজড নয়) D&C ফাংশন লেখা হয়েছে — এটি প্রতিটি রিকার্সিভ কল এবং সর্বোচ্চ ডেপথ গুনে রাখে।

import random
import math

def max_divide_and_conquer(arr, counter, depth=0):
    counter['calls'] += 1
    counter['max_depth'] = max(counter['max_depth'], depth)
    if len(arr) == 1:
        return arr[0]
    mid = len(arr) // 2
    left_max = max_divide_and_conquer(arr[:mid], counter, depth + 1)
    right_max = max_divide_and_conquer(arr[mid:], counter, depth + 1)
    return left_max if left_max > right_max else right_max

random.seed(42)
sizes = [8, 16, 32, 64, 128]

print(f"{'n':>5} | {'সঠিক?':>7} | {'কল':>6} | {'2n-1':>6} | {'ডেপথ':>6} | {'log2(n)':>8}")
for n in sizes:
    arr = list(range(n))
    random.shuffle(arr)
    counter = {'calls': 0, 'max_depth': 0}
    result = max_divide_and_conquer(arr, counter)
    predicted_calls = 2 * n - 1
    predicted_depth = int(math.log2(n))
    correct = (result == max(arr))
    print(f"{n:>5} | {str(correct):>7} | {counter['calls']:>6} | {predicted_calls:>6} | {counter['max_depth']:>6} | {predicted_depth:>8}")