রিকার্সন ট্রি মেথড

১ · রিকার্সন ট্রি মেথড — ধারণা

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

২ · উদাহরণ — $T(n) = 2T(n/2) + n^2$

এই রিকারেন্সে প্রতিটি কল তার দুটো উপসমস্যার (প্রতিটির আকার $n/2$) বাইরে নিজে $n^2$ পরিমাণ কাজ করে (যেমন "কম্বাইন" ধাপে)। রুট নোডের খরচ তাই $n^2$, আকার $n$। প্রতিটি চাইল্ড নোডের খরচ $(n/2)^2$, আকার $n/2$ — এবং এমন দুটো চাইল্ড আছে। নিচের ডায়াগ্রামে প্রথম কয়েকটি স্তর দেখানো হয়েছে:

সাধারণভাবে, গভীরতা $i$-তে $2^i$টি নোড থাকে, প্রতিটির আকার $n/2^i$ এবং খরচ $(n/2^i)^2$। সেই স্তরের মোট খরচ:

$$2^i \times \left(\frac{n}{2^i}\right)^2 = 2^i \times \frac{n^2}{4^i} = \frac{n^2}{2^i}$$

গাছটির গভীরতা $\log_2 n$ (যেখানে আকার $1$-এ পৌঁছে বেস কেস হয়ে যায়), তাই মোট খরচ হলো $i=0$ থেকে $i=\log_2 n - 1$ পর্যন্ত প্রতি স্তরের খরচের যোগফল, প্লাস লিফ স্তরের খরচ ($n$টি লিফ, প্রতিটি $\Theta(1)$):

$$T(n) = \sum_{i=0}^{\log_2 n - 1} \frac{n^2}{2^i} \;+\; \Theta(n) = n^2\left(1+\frac12+\frac14+\cdots\right) + \Theta(n)$$

বন্ধনীর ভেতরের সিরিজটি একটি জ্যামিতিক সিরিজ (geometric series), অনুপাত $\frac12 < 1$। এমন সিরিজের একটি গুরুত্বপূর্ণ বৈশিষ্ট্য — যতগুলো পদই থাকুক না কেন (এখানে $\log_2 n$টি পদ), যোগফল কখনোই প্রথম পদের দ্বিগুণের বেশি হয় না: $1+\frac12+\frac14+\cdots < \frac{1}{1-1/2} = 2$। তাই:

$$T(n) < 2n^2 + \Theta(n) = \Theta(n^2)$$

অর্থাৎ, রুট স্তরের খরচই ($n^2$) পুরো যোগফলে প্রাধান্য পায় — বাকি সব স্তর মিলিয়েও রুটের সমান কাজের বেশি যোগ করতে পারে না, কারণ প্রতি স্তরে খরচ জ্যামিতিকভাবে কমছে। এটাই এই ধরনের রিকারেন্সের (যেখানে "কম্বাইন" খরচ উপসমস্যার সংখ্যার তুলনায় দ্রুত বাড়ে) একটি সাধারণ প্যাটার্ন — L13-এর মাস্টার থিওরেমে এই একই রিকারেন্স আবার দেখা যাবে, ঠিক এই কারণেই এটি "কেস ৩"-এর একটি ক্লাসিক উদাহরণ হবে।

৩ · সত্যিকারের কোড — অনুপাত পরীক্ষা করা

উপরের ডেরিভেশন অনুযায়ী মোট খরচের প্রধান পদ $2n^2$ — অর্থাৎ $T(n)/n^2$ অনুপাতের $2$-এর দিকে এগিয়ে যাওয়ার কথা। নিচের কোড রিকারেন্সটি সরাসরি রিকার্সনের মাধ্যমে গণনা করে যাচাই করছে:

def T(n):
    if n <= 1:
        return 1                     # বেস কেস T(1) = 1
    return 2 * T(n // 2) + n ** 2    # রিকারেন্স নিজেই -- কোনো সূত্র অনুমান নয়

sizes = [2, 4, 8, 16, 32, 64, 128, 256]

print(f"{'n':>5} | {'T(n)':>9} | {'n^2':>9} | {'T(n)/n^2':>10}")
for n in sizes:
    t = T(n)
    ratio = t / (n ** 2)
    print(f"{n:>5} | {t:>9} | {n**2:>9} | {ratio:>10.5f}")