মেমোইজেশন এবং ট্যাবুলেশন হলো ডায়নামিক প্রোগ্রামিং (DP) এর দুটি গুরুত্বপূর্ণ কৌশল, যা পুনরাবৃত্ত সমস্যাগুলির কার্যকারিতা বাড়াতে ব্যবহৃত হয়। এ দুটি কৌশল একই ধরনের সমস্যা সমাধানে ভিন্ন ভিন্ন পন্থা ব্যবহার করে।
১. মেমোইজেশন (Memoization)
মেমোইজেশন হলো টপ-ডাউন পদ্ধতির একটি কৌশল, যেখানে একটি ফাংশন কোনো সমস্যা সমাধান করার সময় ফলাফলগুলো ক্যাশ করে রাখে। যদি আবার সেই একই সাব-প্রবলেম সমাধানের প্রয়োজন হয়, তাহলে আগের ফলাফলটি সরাসরি ব্যবহার করা হয়। এতে করে পুনরাবৃত্ত সাব-প্রবলেমগুলো বারবার সমাধান করতে হয় না, ফলে টাইম কমপ্লেক্সিটি কমে যায়।
কিভাবে মেমোইজেশন কাজ করে:
- কোনো ফাংশন প্রথমবার একটি সাব-প্রবলেম সমাধান করলে সেই ফলাফলটি একটি ডেটা স্ট্রাকচারে (যেমন অ্যারে বা ডিকশনারি) সংরক্ষণ করে।
- যদি পরবর্তীতে আবার একই সাব-প্রবলেম সমাধানের প্রয়োজন হয়, তাহলে ক্যাশ থেকে সরাসরি ফলাফলটি ব্যবহার করা হয়।
উদাহরণ: ফিবোনাচ্চি সিরিজ গণনা
পুনরাবৃত্তভাবে ফিবোনাচ্চি সিরিজ গণনা করলে অনেকবার একই মান বের করতে হয়, ফলে টাইম কমপ্লেক্সিটি বৃদ্ধি পায়। কিন্তু মেমোইজেশন ব্যবহারে আমরা একবার গণনা করা মান সংরক্ষণ করে রাখতে পারি।
def fib(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
টাইম কমপ্লেক্সিটি: O(n) (কারণ প্রতিটি মান একবার করে ক্যালকুলেট করা হয় এবং ক্যাশ থেকে পড়া হয়)
২. ট্যাবুলেশন (Tabulation)
ট্যাবুলেশন হলো বটম-আপ পদ্ধতির একটি কৌশল, যেখানে সমস্যাটি ছোট ছোট সাব-প্রবলেমে ভাগ করা হয় এবং প্রতিটি সাব-প্রবলেমের সমাধান একটি টেবিলে সংরক্ষণ করা হয়। পরে সাব-প্রবলেমগুলোর সাহায্যে মূল সমস্যার সমাধান বের করা হয়।
কিভাবে ট্যাবুলেশন কাজ করে:
- প্রথমে ছোট ছোট সাব-প্রবলেমগুলো সমাধান করা হয় এবং ফলাফলগুলো একটি টেবিলে সংরক্ষণ করা হয়।
- টেবিল থেকে ধীরে ধীরে বড় সমস্যার সমাধান বের করা হয়।
উদাহরণ: ফিবোনাচ্চি সিরিজ গণনা (ট্যাবুলেশন)
def fib(n):
table = [0] * (n + 1)
table[1] = 1
for i in range(2, n + 1):
table[i] = table[i - 1] + table[i - 2]
return table[n]
টাইম কমপ্লেক্সিটি: O(n) এবং স্পেস কমপ্লেক্সিটি O(n) (তবে স্পেস কমপ্লেক্সিটি কমানোর জন্য শুধুমাত্র দুটি ভেরিয়েবল ব্যবহার করে করা সম্ভব)
মেমোইজেশন বনাম ট্যাবুলেশন
| বৈশিষ্ট্য | মেমোইজেশন | ট্যাবুলেশন |
|---|---|---|
| পদ্ধতি | টপ-ডাউন | বটম-আপ |
| ব্যবহার | রিকার্সিভ ফাংশন | লুপ ভিত্তিক সমাধান |
| ফলাফল সংরক্ষণ | প্রয়োজনীয় সাব-প্রবলেমের জন্য | প্রতিটি সাব-প্রবলেমের জন্য |
| টাইম কমপ্লেক্সিটি | O(n) | O(n) |
| কোডের জটিলতা | তুলনামূলক কম | কিছুটা বেশি |
| উপযুক্ত ক্ষেত্র | যখন বড় সমস্যা সাব-প্রবলেমে বিভক্ত | নির্দিষ্ট ধাপে সমস্যা সমাধান |
সারসংক্ষেপ
- মেমোইজেশন টপ-ডাউন পদ্ধতি যেখানে রিকার্সন ব্যবহার করে সমাধান করা হয় এবং প্রয়োজনীয় সাব-প্রবলেম ক্যাশ করা হয়।
- ট্যাবুলেশন বটম-আপ পদ্ধতি যেখানে লুপের মাধ্যমে ছোট সাব-প্রবলেমগুলোর সমাধান করে মূল সমস্যার সমাধান বের করা হয়।
দুইটি কৌশলই কার্যকর, তবে নির্দিষ্ট সমস্যার ধরণ এবং কোডিং স্টাইল অনুযায়ী একটিকে বেছে নেওয়া হয়।
Read more
