Master Theorem দিয়ে নিমিষেই রিকারেন্স টাইম কমপ্লেক্সিটি সমাধান
সংক্ষেপে মনে রাখুন
দ্রুত রিভিশনের জন্য মূল কথা
- Master Theorem-এর রূপ T(n) = aT(n/b) + f(n) চিনতে পারা
- n^(log_b a) এর সাথে f(n) তুলনা করে মুহূর্তেই সঠিক কেস নির্ধারণ করা
- কখন Master Theorem প্রয়োগ করা যাবে না তা জানা
T(n) = a T(n/b) + Θ(n^k) সমীকরণে শুধু c = log_b(a) এবং k এর তুলনা করুন: ১. log_b(a) > k হলে: নিচের লিফ লেভেলের…
মাস্টার থিওরেম শুধুমাত্র T(n) = a T(n/b) + f(n) ফরম্যাটে খাটে যেখানে a >= 1, b > 1 ধ্রুবক। কিন্তু T(n) = 2T(n - 1) + 1 (সাবট্র্যাক্ট) বা T(n) = √n T(√n) + n এ এটি সরাসরি প্রয়োগ করা যায় না।
মাস্টার থিওরেম সূত্র (Formulation)
ডিভাইড অ্যান্ড কনকার রিকারেন্সের আদর্শ রূপ: $$T(n) = aT(n/b) + f(n)$$ যেখানে $a \ge 1, b > 1$।
৩টি মূল কেস (Three Cases)
- Case 1 (Tree Heavy): যদি $f(n) = O(n^{\log_b a - \epsilon})$ হয়, তবে $T(n) = \Theta(n^{\log_b a})$
- Case 2 (Balanced): যদি $f(n) = \Theta(n^{\log_b a})$ হয়, তবে $T(n) = \Theta(n^{\log_b a} \log n)$
- Case 3 (Root Heavy): যদি $f(n) = \Omega(n^{\log_b a + \epsilon})$ এবং regularity শর্ত পূরণ করে, তবে $T(n) = \Theta(f(n))$
> ⚡ ৫-সেকেন্ড শর্টকাট (Exam Shortcut): > - Merge Sort: $T(n) = 2T(n/2) + n \implies n^{\log_2 2} = n \implies \Theta(n \log n)$ > - Binary Search: $T(n) = T(n/2) + 1 \implies n^{\log_2 1} = 1 \implies \Theta(\log n)$ > - Karatsuba Multiplication: $T(n) = 3T(n/2) + O(n) \implies \Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})$
> ⚠️ পরীক্ষার ফাঁদ (Exam Trap): > যদি $T(n) = 2T(n/2) + n \log n$ থাকে, তবে সাধারণ Master Theorem চলে না (পলিনোমিয়াল ব্যবধান নেই); তখন Extended Master Theorem দিয়ে উত্তর হয় $\Theta(n \log^2 n)$।
পরের ধাপ
এই টপিকে ৫টি প্রশ্ন অনুশীলন করুন
পড়া মনে আছে কি না, ছোট একটি সেটে দেখে নিন। প্রতিটি উত্তরের সাথে ব্যাখ্যা থাকবে, আর ভুল প্রশ্নগুলো রিভিশনের তালিকায় যাবে