জটিলতা ও বিশ্লেষণ৮ মিনিট পড়া

রিকারেন্স রিলেশন (Recurrence Relations)

নিজে নিজেকে ডাকা একটি রেসিপি — সমাধান করতে পারার মতো সহজ না হওয়া পর্যন্ত
merge sort:T(n)=2T(n/2)+O(n) → O(n log n)binary search:T(n)=T(n/2)+O(1) → O(log n)Master Theorem:T(n)=aT(n/b)+f(n)

ভোজের রান্নার এমন একটি রেসিপির কথা ভাবুন যা বলছে: "N জনের জন্য রান্না করতে, অতিথিদের দুই ভাগে ভাগ করুন, প্রতিটি ভাগের জন্য আলাদাভাবে রান্না করুন, তারপর দুই ভাগের খাবার একসাথে মেশান।" রেসিপিটি নিজেই নিজেকে নির্দেশ করছে! এই স্বয়ং-নির্দেশকারী (self-referencing) বিষয়টাই হলো অ্যালগরিদমের ক্ষেত্রে একটি রিকারেন্স রিলেশন (recurrence relation)।

যখন একটি রিকার্সিভ অ্যালগরিদম n আকারের একটি সমস্যাকে উপ-সমস্যায় (sub-problems) ভাগ করে এবং ফলাফলগুলো একত্রিত করে সমাধান করে, তখন এর চলন-সময় (running time) T(n) নির্ভর করে T(ছোট n) এর ওপর। একটি রিকারেন্স রিলেশন হলো সেই সমীকরণ যা এই নির্ভরতাকে ধারণ করে — এবং এর সমাধান থেকে আমরা চূড়ান্ত Big-O পেয়ে থাকি।

T(n) = aT(n/b) + f(n) পড়া

এটি ডিভাইড-অ্যান্ড-ভনকার (divide-and-conquer) এর আদর্শ টেমপ্লেট। a = আপনি কয়টি উপ-সমস্যা তৈরি করবেন। n/b = প্রতিটি উপ-সমস্যার আকার। f(n) = রিকার্সিভ কলের বাইরে করা কাজ (ভাগ করা, একত্রিত করা)।

মার্জ সর্ট: T(n) = 2T(n/2) + O(n) — দুটি ভাগ (a=2), প্রতিটি অর্ধেকের সমান আকারের (b=2), এর সাথে একত্রিত করার জন্য O(n) কাজ (f(n)=n)।

বাইনারি সার্চ: T(n) = T(n/2) + O(1) — একটি উপ-সমস্যা (a=1), আকারের অর্ধেক (b=2), শুধুমাত্র একটি তুলনা (f(n)=1)।

মাস্টার থিওরেম (The Master Theorem) — আপনার সহজ উপায়

মাস্টার থিওরেম T(n) = aT(n/b) + f(n) এর সমাধান করে f(n) কে "প্রাকৃতিক" রিকার্সনের খরচ n^(log_b a) এর সাথে তুলনা করে:

ক্ষেত্র ১ — রিকার্সন প্রভাবশালী: f(n) হলো n^(log_b a) এর চেয়ে ছোট। তাহলে T(n) = Θ(n^(log_b a))। বেশিরভাগ কাজ রিকার্সন ট্রির একেবারে গভীরে বা নিচে ঘটে থাকে।

ক্ষেত্র ২ — উভয়ই সমান: f(n) = Θ(n^(log_b a))। তাহলে T(n) = Θ(n^(log_b a) · log n)। ট্রির প্রতিটি স্তর সমান কাজ করে, তাই আমরা স্তরের সংখ্যা দিয়ে গুণ করি।

ক্ষেত্র ৩ — একত্রিত করা প্রভাবশালী: f(n) হলো n^(log_b a) এর চেয়ে বড় (একটি রেগুলারিটি শর্তসহ)। তাহলে T(n) = Θ(f(n))। বেশিরভাগ কাজ উপরের স্তরে ঘটে থাকে।

রিকার্সন ট্রি — ভিজ্যুয়াল ইনট্যুইশন

রিকার্সনটিকে একটি ট্রি হিসেবে আঁকুন। প্রতিটি নোড দেখায় যে ওই স্তরে কতটা নন-রিকার্সিভ কাজ করা হয়েছে। মার্জ সর্টের জন্য: স্তর ০-এ ১টি নোড O(n) কাজ করছে; স্তর ১-এ ২টি নোড প্রত্যেকে O(n/2) কাজ করছে = মোট O(n); স্তর ২-এ ৪টি নোড প্রত্যেকে O(n/4) কাজ করছে = মোট O(n)। প্রতিটি স্তর O(n) কাজ করছে, এবং O(log n) টি স্তর রয়েছে — তাই মোট খরচ হলো O(n log n)। এই ট্রিটি গুণফলকে দৃশ্যগতভাবে সহজ করে তোলে।

দ্রষ্টব্য: মাস্টার থিওরেম হলো রিকার্সনের জন্য একটি ক্যালকুলেটর: a, b এবং f(n)-এর মান বসান, f(n)-কে n^(log_b a)-এর সাথে তুলনা করুন এবং উত্তর পেয়ে যান। মার্জ সর্ট: log_2(2) = 1, f(n) = n = n^1 — তারা মিলে গেছে! এটি ক্ষেত্র ২ → Θ(n log n)।

মার্জ সর্টের রিকারেন্স সমাধান — রিকার্সন ট্রি

def merge_sort(arr, depth=0):
    indent = "  " * depth
    n = len(arr)
    if n <= 1:
        print(f"{indent}base case: {arr}")
        return arr
    mid = n // 2
    left = merge_sort(arr[:mid], depth + 1)
    right = merge_sort(arr[mid:], depth + 1)
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    merged += left[i:] + right[j:]
    print(f"{indent}merge({left}, {right}) -> {merged}  [O(n) work at this level]")
    return merged


result = merge_sort([5, 2, 8, 1, 9])
print("Sorted:", result)
Output
    base case: [5]
    base case: [2]
  merge([5], [2]) -> [2, 5]  [O(n) work at this level]
    base case: [8]
    base case: [1]
    base case: [9]
  merge([1], [9]) -> [1, 9]  [O(n) work at this level]
  merge([8], [1, 9]) -> [1, 8, 9]  [O(n) work at this level]
merge([2, 5], [1, 8, 9]) -> [1, 2, 5, 8, 9]  [O(n) work at this level]
Sorted: [1, 2, 5, 8, 9]

Complexity

🔍 বাইনারি সার্চ (Binary search) T(n)=T(n/2)+O(1)
ক্ষেত্র ২: log_2(1)=0, f(n)=O(1)=Θ(n^0) — উভয়ই মিলে যায় → log n দিয়ে গুণ করুন
লগারিদমিক (Logarithmic) O(log n)
🔀 মার্জ সর্ট (Merge sort) T(n)=2T(n/2)+O(n)
ক্ষেত্র ২: log_2(2)=1, f(n)=Θ(n^1) — মিলে যায় → Θ(n log n)
লিনিয়ারদমিক (Linearithmic) O(n log n)
🧮 স্ট্রাসেন (Strassen) T(n)=7T(n/2)+O(n²)
ক্ষেত্র ১: log_2(7) ≈ 2.807 > 2 — রিকার্সন প্রভাবশালী
সাব-কিউবিক (Sub-cubic) O(n^2.807)
📦 নেভ ম্যাট্রিক্স গুণন (Naive matrix multiply) T(n)=8T(n/2)+O(n²)
ক্ষেত্র ১: log_2(8)=3 — রিকার্সন প্রভাবশালী
কিউবিক (Cubic) O(n³)
📝 লিনিয়ার স্ক্যান (Linear scan) T(n)=T(n−1)+O(1)
সাধারণ মাস্টার রূপে নেই — প্রতিস্থাপন থেকে T(n)=O(n) পাওয়া যায়
লিনিয়ার (Linear) O(n)

ছোট কুইজ

T(n) = 2T(n/2) + O(n) এমন একটি অ্যালগরিদম বর্ণনা করে যা...

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

বিগ-ও, থিটা, ওমেগা (Big-O, Theta, Omega)
অতিথির সংখ্যা বাড়লে আপনার রান্নার রেসিপি কতটা ধীর হয়ে যায়?
→
মার্জ সর্ট (Merge Sort)
ভাগ করুন, প্রতি অর্ধেক সাজান, তারপর একত্রিত (merge) করুন — প্রতিবারই \(O(n \log n)\) এর নিশ্চয়তা
→
ডিভাইড অ্যান্ড কঙ্কার (D&C) প্যাটার্ন (Divide and Conquer Pattern)
সমস্যাটিকে ছোট ছোট টুকরাতে বিভক্ত করুন, টুকরোগুলোকে সমাধান করুন এবং তারপর সব ফলাফলগুলোকে একত্রিত করুন
→