অ্যামর্টাইজড কস্ট (Amortized Cost) একটি বিশ্লেষণ পদ্ধতি যা ডেটা স্ট্রাকচার এবং অ্যালগরিদমের গড় কার্যকারিতা বা ব্যয় নির্ধারণ করতে ব্যবহৃত হয়, বিশেষত যখন কিছু অপারেশন খরচের দিক থেকে ব্যয়বহুল হতে পারে, তবে অন্যান্য অপারেশনগুলি সস্তা। এই পদ্ধতি ব্যবহার করে আমরা একটি অপারেশনের গড় খরচ বুঝতে পারি যখন কিছু অপারেশন একসাথে করা হয়।
অ্যামর্টাইজড কস্টের প্রকারভেদ
অ্যামর্টাইজড কস্ট বিশ্লেষণের প্রধান তিনটি পদ্ধতি হল:
ইনভ্যারিয়েন্ট (Aggregate Analysis):
- এই পদ্ধতিতে, আমরা সমস্ত অপারেশনের জন্য মোট খরচ হিসাব করি এবং তারপরে অপারেশনের সংখ্যা দ্বারা ভাগ করি। এটি গড় খরচ দেয়।
- উদাহরণস্বরূপ, যদি \( n \) সংখ্যক অপারেশনের মোট খরচ \( T(n) \) হয়, তবে অ্যামর্টাইজড কস্ট হবে \( T(n) / n \)।
পেসিং (Accounting Method):
- এই পদ্ধতিতে, আমরা অপারেশনগুলির জন্য একটি "বাজেট" নির্ধারণ করি এবং কিছু অপারেশনকে "সংরক্ষণ" করে রাখি, যাতে তারা ভবিষ্যতে ব্যয়বহুল অপারেশনের খরচকে সাহায্য করতে পারে।
- উদাহরণস্বরূপ, যদি একটি ডেটা স্ট্রাকচার বৃদ্ধি করার জন্য প্রয়োজন হয়, তবে আমরা প্রতিটি ছোট অপারেশনের জন্য কিছু অতিরিক্ত খরচকে সংরক্ষণ করতে পারি।
ফ্লাইনিং (Potential Method):
- এই পদ্ধতিতে, আমরা একটি "পোটেনশিয়াল" ফাংশন ব্যবহার করি যা ডেটা স্ট্রাকচারের বর্তমান অবস্থাকে প্রতিনিধিত্ব করে। অপারেশনগুলি এই পোটেনশিয়ালের উপর ভিত্তি করে খরচকে নির্ধারণ করে।
- উদাহরণস্বরূপ, যদি \( \Phi \) হল পোটেনশিয়াল ফাংশন, তাহলে অ্যামর্টাইজড কস্ট হবে \( C + \Delta \Phi \), যেখানে \( C \) হল বর্তমান অপারেশনের খরচ এবং \( \Delta \Phi \) হল পোটেনশিয়ালের পরিবর্তন।
উদাহরণ
ডাইনামিক অ্যারের বৃদ্ধি
ধরি, আমরা একটি ডাইনামিক অ্যারে তৈরি করছি যা ইনসার্ট অপারেশন পরিচালনা করছে। শুরুতে, অ্যারের আকার \( n \) হয় এবং আমরা যখন একটি নতুন উপাদান যোগ করি, তখন যদি অ্যারের আকার পূর্ণ হয়, তখন আমাদের অ্যারের আকার দ্বিগুণ করতে হবে।
- সস্তা ইনসার্ট: \( O(1) \) (যখন আকার পূর্ণ নয়)
- মহা ইনসার্ট: \( O(n) \) (যখন আকার পূর্ণ এবং পুনরায় বরাদ্দ করতে হবে)
এখন, যদি আমাদের \( n \) সংখ্যক ইনসার্ট অপারেশন থাকে, তাহলে:
- মোট খরচ \( O(n) \) সস্তা ইনসার্ট এবং \( O(n) \) মহা ইনসার্টের জন্য হবে \( O(n) + O(n) = O(n) \)।
- অ্যামর্টাইজড কস্ট হবে \( O(n) / n = O(1) \)।
উপসংহার
অ্যামর্টাইজড কস্ট একটি গুরুত্বপূর্ণ ধারণা যা ডেটা স্ট্রাকচার এবং অ্যালগরিদমের কার্যকারিতা বিশ্লেষণে সাহায্য করে। এটি আমাদের একটি অপারেশনের গড় খরচ বুঝতে সহায়তা করে, এমনকি যখন কিছু অপারেশন ব্যয়বহুল হয়। এটি বিশেষত ডাইনামিক অ্যারের মতো পরিস্থিতিতে কার্যকর, যেখানে অপারেশনগুলির খরচ পরিবর্তিত হতে পারে।
Read more
