ডিভাইড-অ্যান্ড-কনকার রিকারেন্স ও Master Theorem
এই পাঠে যা শিখবেন
- ডিভাইড-অ্যান্ড-কনকার রিকারেন্সের সাধারণ রূপ $T(n)=aT(n/b)+f(n)$-এর প্রতিটি অংশের অর্থ
- Master Theorem-এর তিনটি কেস — নিখুঁত শর্তসহ
- মার্জ সর্ট, বাইনারি সার্চ ও একটি তৃতীয় উদাহরণে থিওরেমের প্রয়োগ
- কীভাবে $n^{\log_b a}$ গণনা করে সঠিক কেস চিহ্নিত করতে হয়
১ · ডিভাইড-অ্যান্ড-কনকার রিকারেন্সের সাধারণ রূপ
L29-এ আমরা দেখেছি $T(n)=2T(n/2)+n$ মার্জ সর্টের রানটাইম মডেল করে। এটি আরও সাধারণভাবে লেখা যায় —
$$T(n) = a \cdot T(n/b) + f(n), \qquad a \geq 1,\ b > 1$$
এখানে $a$ হলো প্রতিবার কতগুলো সাব-প্রবলেমে বিভক্ত হচ্ছে তার সংখ্যা, $b$ হলো প্রতিটি সাব-প্রবলেম মূল ইনপুটের কত ভাগের এক ভাগ (যেমন $b=2$ মানে অর্ধেক), এবং $f(n)$ হলো ভাগ করা (split/divide) এবং ফলাফল একত্র করা (combine) — এই দুই কাজে যত সময় লাগে তার পরিমাণ (রিকার্সিভ কল বাদে)।
L30-এর ক্যারেক্টারিস্টিক ইকুয়েশন পদ্ধতি শুধু $a_n = a_{n-1}+\dots$ ধরনের রিকারেন্সে কাজ করে ($n-1$, $n-2$ — বিয়োগ)। কিন্তু $T(n/2)$-এর মতো ভাগ-ভিত্তিক রিকারেন্সে সেই পদ্ধতি সরাসরি প্রযোজ্য নয়। Master TheoremMaster Theorem$T(n)=aT(n/b)+f(n)$ আকারের রিকারেন্সের জন্য একটি "রেসিপি" — $f(n)$-কে $n^{\log_b a}$-এর সাথে তুলনা করে সরাসরি তিনটি সম্ভাব্য কেসের একটিতে $T(n)$-এর টাইট বাউন্ড ($\Theta$) বলে দেয়, কোনো ধাপে ধাপে ডেরিভেশন ছাড়াই। ঠিক এই ধরনের রিকারেন্সের জন্য একটি সরাসরি "রেসিপি" — কোনো ধাপে ধাপে ডেরিভেশন ছাড়াই।
২ · Master Theorem — তিনটি কেস
মূল তুলনার বিন্দু হলো $n^{\log_b a}$ — এটি হলো "যদি শুধু রিকার্সিভ কলগুলোই থাকতো, combine-এর কোনো খরচ না থাকতো" তাহলে যে জটিলতা হতো। তিনটি কেস নির্ভর করে $f(n)$ এই বিন্দুর তুলনায় কেমন বাড়ে তার উপর —
যদি $f(n) = O\!\big(n^{\log_b a - \epsilon}\big)$ কোনো $\epsilon>0$-এর জন্য, তাহলে $T(n) = \Theta\!\big(n^{\log_b a}\big)$। ($f(n)$ তুলনামূলক ছোট — leaf নোডগুলোর মোট কাজ প্রাধান্য পায়।)
যদি $f(n) = \Theta\!\big(n^{\log_b a}\big)$, তাহলে $T(n) = \Theta\!\big(n^{\log_b a} \cdot \log n\big)$। (প্রতিটি স্তরে সমান কাজ — মোট $\log n$টি স্তর, তাই একটি $\log n$ গুণিতক যোগ হয়।)
যদি $f(n) = \Omega\!\big(n^{\log_b a + \epsilon}\big)$ কোনো $\epsilon>0$-এর জন্য (এবং একটি নিয়মিততা শর্ত/regularity condition সন্তুষ্ট হয়), তাহলে $T(n) = \Theta\!\big(f(n)\big)$। (root নোডের combine কাজই প্রাধান্য পায়।)
৩ · ওয়ার্কড উদাহরণ ১ — মার্জ সর্ট
রিকারেন্স: $T(n) = 2T(n/2) + n$।
এখানে $a=2$, $b=2$, তাই $\log_b a = \log_2 2 = 1$, অর্থাৎ তুলনার বিন্দু $n^1 = n$। আর $f(n) = n$ — যা ঠিক $n^{\log_b a} = n^1$-এর সমান। তাই এটি কেস ২।
$$T(n) = \Theta\!\big(n^1 \cdot \log n\big) = \Theta(n \log n)$$
৪ · ওয়ার্কড উদাহরণ ২ — বাইনারি সার্চ
রিকারেন্স: $T(n) = T(n/2) + O(1)$।
এখানে $a=1$, $b=2$, তাই $\log_b a = \log_2 1 = 0$, তুলনার বিন্দু $n^0 = 1$। আর $f(n) = O(1) = n^0$ — আবারও ঠিক $n^{\log_b a}$-এর সমান। তাই এটিও কেস ২।
$$T(n) = \Theta\!\big(n^0 \cdot \log n\big) = \Theta(\log n)$$
৫ · ওয়ার্কড উদাহরণ ৩ — একটি কেস ৩ উদাহরণ
রিকারেন্স: $T(n) = T(n/2) + n$।
এখানে $a=1$, $b=2$, তাই $\log_b a = 0$, তুলনার বিন্দু $n^0=1$। কিন্তু এবার $f(n) = n$, যা $n^{0+\epsilon}$-এর জন্য $\epsilon=1$ বসিয়ে $\Omega(n^{0+1}) = \Omega(n)$ শর্ত সন্তুষ্ট করে ($n$ স্পষ্টভাবে $1$-এর চেয়ে দ্রুত বাড়ে)। তাই এটি কেস ৩।
$$T(n) = \Theta(f(n)) = \Theta(n)$$
লক্ষ্য করুন কতটা ভিন্ন ফলাফল আসে যখন শুধু $f(n)$ পরিবর্তন হয় ($a, b$ একই রেখে)। $T(n)=T(n/2)+O(1)$ দেয় $\Theta(\log n)$ (অতি দ্রুত), কিন্তু $T(n)=T(n/2)+n$ দেয় $\Theta(n)$ (অনেক ধীর) — যদিও উভয়েই মাত্র একটি সাব-প্রবলেম ($a=1$)! পার্থক্যটা পুরোপুরি combine ধাপ ($f(n)$)-এর খরচে।
import math
def log_b_a(a, b):
return math.log(a, b)
examples = [
("মার্জ সর্ট: T(n)=2T(n/2)+n", 2, 2, "n"),
("বাইনারি সার্চ: T(n)=T(n/2)+O(1)", 1, 2, "O(1) = n^0"),
("উদাহরণ ৩: T(n)=T(n/2)+n", 1, 2, "n"),
]
for label, a, b, f_desc in examples:
exponent = log_b_a(a, b)
print(f"{label}")
print(f" a={a}, b={b} => log_b(a) = {exponent:.4f} => তুলনার বিন্দু n^{exponent:.4f}")
print(f" f(n) = {f_desc}")
print()
print("মার্জ সর্ট : f(n)=n = n^1.0000 = তুলনার বিন্দু => কেস ২ => Theta(n log n)")
print("বাইনারি সার্চ : f(n)=O(1)=n^0.0000 = তুলনার বিন্দু => কেস ২ => Theta(log n)")
print("উদাহরণ ৩ : f(n)=n, তুলনার বিন্দু n^0 থেকে বড় => কেস ৩ => Theta(n)")math.log(a, b) দিয়ে $\log_b a$ সংখ্যাগতভাবে গণনা করা হয়েছে — এটি নিশ্চিত করে যে
$\log_2 2 = 1.0$ এবং $\log_2 1 = 0.0$, যা আমাদের হাতে-করা বিশ্লেষণের সাথে মিলে যায়। কোন কেস প্রযোজ্য তা ঠিক
করা (যেমন $f(n)$ ঠিক $n^{\log_b a}$-এর সমান কি না) এখনো একটি গাণিতিক তুলনা, সরাসরি কোডে প্রতীকীভাবে (symbolically)
যাচাই করার মতো সহজ নয় — তাই সেটি এখানে প্রিন্ট করা সিদ্ধান্ত হিসেবে দেখানো হয়েছে।
Master Theorem একটি সরাসরি "শর্টকাট" — ক্যারেক্টারিস্টিক ইকুয়েশনের মতো ধাপে ধাপে সমাধান না করে, শুধু $a, b, f(n)$ দেখে সরাসরি $\Theta$ বলে দেয়। এই থিওরেমটিই M8/L41-এ মার্জ সর্ট ও বাইনারি সার্চের রিয়েল-ওয়ার্ল্ড জটিলতা নির্ণয় করতে পুনরায় ব্যবহার হবে — এখানকার দুটি worked example ঠিক সেখানেই আবার ফিরে আসবে।
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।
প্র ০১ মার্জ সর্ট ও বাইনারি সার্চ দুটোই কেস ২-তে পড়ে, কিন্তু তাদের চূড়ান্ত জটিলতা ভিন্ন ($n\log n$ বনাম $\log n$) — কেন?
কেস ২ বলে $T(n) = \Theta(n^{\log_b a} \cdot \log n)$ — এখানে $n^{\log_b a}$ পদটি দুটি ক্ষেত্রে ভিন্ন। মার্জ সর্টে $a=2, b=2 \Rightarrow \log_b a = 1$, তাই $n^1 \cdot \log n = n \log n$। বাইনারি সার্চে $a=1, b=2 \Rightarrow \log_b a = 0$, তাই $n^0 \cdot \log n = 1 \cdot \log n = \log n$। পার্থক্যটা আসে $a$ থেকে — মার্জ সর্ট প্রতি স্তরে দুটি সাব-প্রবলেম তৈরি করে (তাই বেশি মোট কাজ), বাইনারি সার্চ প্রতি স্তরে মাত্র একটি সাব-প্রবলেমে যায় (বাকি অর্ধেক সম্পূর্ণ বাতিল হয়ে যায়)।
প্র ০২ $T(n) = T(n/2) + O(1)$ এবং $T(n) = T(n/2) + n$ — এই দুটির মধ্যে $a$ ও $b$ হুবহু একই, শুধু $f(n)$ ভিন্ন, তবু ফলাফল $\log n$ বনাম $n$ — এত বড় পার্থক্য কেন?
কারণ Master Theorem-এর কেস ২ ও কেস ৩-এর মধ্যে সিদ্ধান্তটাই সম্পূর্ণ নির্ভর করে $f(n)$ কীভাবে $n^{\log_b a}=n^0=1$-এর তুলনায় বাড়ে তার উপর। যখন $f(n)=O(1)$ (ধ্রুবক, একদম বাড়ে না) সেটি ঠিক $n^0$-এর সমান হারে থাকে — কেস ২। কিন্তু $f(n)=n$ সেই বিন্দু থেকে অনেক দ্রুত বাড়ে — কেস ৩, যেখানে সবচেয়ে ব্যয়বহুল combine ধাপই (root-এ, যেখানে $f(n)=n$ প্রয়োগ হয়) পুরো রানটাইমে প্রাধান্য বিস্তার করে, ফলে বাকি সব রিকার্সিভ কল তুলনামূলকভাবে নগণ্য হয়ে যায়।
প্র ০৩ কেস ১ ও কেস ৩-এ একটি "$\epsilon>0$" শর্ত (এবং কেস ৩-এ একটি অতিরিক্ত regularity condition) থাকে, কিন্তু কেস ২-এ থাকে না — কেন?
কেস ১ ও কেস ৩ দাবি করে $f(n)$ তুলনার বিন্দু থেকে স্পষ্টভাবে (strictly) ভিন্ন হারে বাড়ে — শুধু "একটু ভিন্ন" নয়, বরং একটি পূর্ণ পলিনমিয়াল গুণিতক ($n^\epsilon$) দ্বারা ভিন্ন। এই কড়া শর্তটি নিশ্চিত করে ফলাফল একটি পরিষ্কার $\Theta$-এ পৌঁছায়, কোনো ধোঁয়াশা ছাড়াই। কেস ২-তে $f(n)$ ইতিমধ্যেই তুলনার বিন্দুর সমান ($\Theta$) — এখানে কোনো ফাঁক ($\epsilon$) খোঁজার দরকার নেই, কারণ প্রতিটি স্তরের অবদান একই মাত্রার, শুধু স্তরসংখ্যা ($\log n$) গুণ হয়ে যোগ হয়। regularity condition (কেস ৩) একটি টেকনিক্যাল শর্ত যা নিশ্চিত করে $f(n)$ "খুব বেশি ওঠানামা করছে না" — এই কোর্সে এর গভীর ডেরিভেশনে যাওয়া হয়নি, তবে বেশিরভাগ বাস্তব $f(n)$ (যেমন পলিনমিয়াল) এই শর্ত স্বয়ংক্রিয়ভাবে পূরণ করে।
অনুশীলন
-
কেস চিহ্নিত করুন: রিকারেন্স $T(n) = 4T(n/2) + n$-এর জন্য $a, b, \log_b a$ বের করুন এবং কোন কেস প্রযোজ্য তা নির্ধারণ করে চূড়ান্ত $\Theta$ বের করুন।
$a=4, b=2 \Rightarrow \log_b a = \log_2 4 = 2$, তুলনার বিন্দু $n^2$। এখানে $f(n)=n=n^1$, যা $n^2$-এর চেয়ে ছোট — নির্দিষ্টভাবে $n = O(n^{2-1})$ ($\epsilon=1$ দিয়ে)। তাই এটি কেস ১, এবং $T(n) = \Theta(n^2)$।
-
কোড প্রসারিত করুন: উপরের কোড সেলে অনুশীলন ১-এর উদাহরণ ($a=4,b=2$) যোগ করে
log_b_aফাংশন দিয়ে তুলনার বিন্দু গণনা করে প্রিন্ট করুন।সম্ভাব্য সমাধান:
a, b = 4, 2 exponent = log_b_a(a, b) print(f"a={a}, b={b} => log_b(a) = {exponent}") # 2.0 print("f(n)=n=n^1 < n^2 => কেস ১ => Theta(n^2)")ফলাফল
2.0আসা উচিত, যা নিশ্চিত করে তুলনার বিন্দু $n^2$ — এবং যেহেতু $f(n)=n$ তার চেয়ে ছোট, কেস ১ প্রযোজ্য।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- কোর্সের সম্পূর্ণ সিলেবাস দেখুন ৪৪টি পাঠ পরবর্তী পাঠ — জেনারেটিং ফাংশন পরিচিতি — এই মডিউলের শেষ পাঠে এগিয়ে যান।
- Data Structures & Algorithms কোর্স সঙ্গী কোর্স মার্জ সর্ট ও বাইনারি সার্চের বাস্তব কোড বাস্তবায়ন দেখতে DSA কোর্সটিও দেখুন।
- সব Courses দেখুন ABCL TECH C, C++, Python, Java, JavaScript, DSA, DBMS, HTML & CSS ও Discrete Mathematics — সব এক জায়গায়।