রিকার্সিভ অ্যালগরিদমের জটিলতা

১ · রিকারেন্স থেকে জটিলতায়

M6-এ (L29-L32) আমরা রিকারেন্স রিলেশন সমাধান করার গণিত শিখেছি — কিন্তু সেখানে এই সমাধানগুলো শুধু গাণিতিক অনুশীলন ছিল। এই পাঠে সেই একই গণিত সরাসরি ব্যবহার হবে: যখন একটি অ্যালগরিদম নিজেকে রিকার্সিভভাবে কল করে, তার "ধাপ সংখ্যা" $T(n)$ প্রায় সবসময় একটি রিকারেন্স রিলেশন মেনে চলে। সেই রিকারেন্স সমাধান করাই অ্যালগরিদমের জটিলতা বের করার পদ্ধতি।

২ · ওয়ার্কড উদাহরণ ১ — নেইভ রিকার্সিভ ফিবোনাচি

L29-এ দেখা ফিবোনাচি সংজ্ঞা $F(n)=F(n-1)+F(n-2)$ সরাসরি কোডে বসালে (memoization ছাড়া), প্রতিটি কল দুটি নতুন রিকার্সিভ কল তৈরি করে। এই ফাংশনের কল সংখ্যা $T(n)$-এর রিকারেন্স: $$T(n) = T(n-1) + T(n-2) + O(1)$$ এটি L31-এর ডিভাইড-অ্যান্ড-কনকার ফর্ম ($T(n)=aT(n/b)+f(n)$) নয় — তাই Master Theorem এখানে প্রযোজ্য নয়। কিন্তু এটি ঠিক L30-এর ধরনের একটি ২য়-ক্রম লিনিয়ার হোমোজিনিয়াস রিকারেন্স। ক্যারেক্টারিস্টিক ইকুয়েশন: $$x^2 = x + 1 \implies x^2 - x - 1 = 0 \implies x = \frac{1 \pm \sqrt5}{2}$$ পজিটিভ মূল $\varphi = \frac{1+\sqrt5}{2} \approx 1.618$ — বিখ্যাত গোল্ডেন রেশিওGolden Ratio (φ)≈১.৬১৮, একটি বিশেষ ধ্রুবক যা ফিবোনাচি সিকোয়েন্সের ক্যারেক্টারিস্টিক ইকুয়েশনের মূল হিসেবে স্বাভাবিকভাবে বেরিয়ে আসে।। এর মানে $T(n) = \Theta(\varphi^n)$ — এক্সপোনেনশিয়াল। তাই নেইভ রিকার্সিভ ফিবোনাচি বড় $n$-এ ব্যবহারিকভাবে অসম্ভব ধীর।

৩ · ওয়ার্কড উদাহরণ ২ ও ৩ — Merge Sort ও Binary Search (L31 পুনর্ব্যবহার)

এবার L31-এর দুটি ফলাফল সরাসরি পুনর্ব্যবহার করি:

• Merge sort: $T(n)=2T(n/2)+\Theta(n)$। এখানে $a=2,b=2$, তাই $\log_b a = \log_2 2 = 1$, এবং $f(n)=n=n^{\log_b a}$ — Master Theorem কেস ২ প্রযোজ্য, তাই $T(n)=\Theta(n\log n)$।
• Binary search: $T(n)=T(n/2)+\Theta(1)$। এখানে $a=1,b=2$, তাই $\log_b a=\log_2 1=0$, এবং $f(n)=\Theta(1)=n^0=n^{\log_b a}$ — আবার কেস ২, তাই $T(n)=\Theta(\log n)$।

৪ · কোড: নেইভ বনাম মেমোয়াইজড — কল সংখ্যায় ব্যবধান

তত্ত্ব অনুযায়ী নেইভ ফিবোনাচি এক্সপোনেনশিয়াল আর মেমোয়াইজড সংস্করণ (L29-এ ইঙ্গিত করা, DSA কোর্সে dynamic programming হিসেবে বিস্তারিত) লিনিয়ার। নিচের কোডে আমরা সংখ্যাটি অনুমান করছি না — সরাসরি একটি কাউন্টার দিয়ে ইনস্ট্রুমেন্ট করে গণনা করছি:

# নেইভ রিকার্সিভ ফিবোনাচি — প্রতিটি ফাংশন-কলে কাউন্টার বাড়বে
naive_calls = 0

def fib_naive(n):
    global naive_calls
    naive_calls += 1
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

n = 20
result_naive = fib_naive(n)
print(f"fib_naive({n}) = {result_naive}  |  মোট ফাংশন-কল: {naive_calls}")

# মেমোয়াইজড ফিবোনাচি — একই n দ্বিতীয়বার গণনা করা হয় না (cache miss-এই শুধু কাউন্ট বাড়বে)
memo = {}
memo_computations = 0

def fib_memo(n):
    global memo_computations
    if n in memo:
        return memo[n]
    memo_computations += 1
    if n < 2:
        memo[n] = n
        return n
    result = fib_memo(n - 1) + fib_memo(n - 2)
    memo[n] = result
    return result

result_memo = fib_memo(n)
print(f"fib_memo({n})  = {result_memo}  |  মোট নতুন গণনা: {memo_computations}")

ratio = naive_calls / memo_computations
print(f"\nনেইভ, মেমোয়াইজডের চেয়ে {ratio:.1f} গুণ বেশি কল করেছে!")