ডেটা স্ট্রাকচারে অ্যামোর্টাইজড টাইম কমপ্লেক্সিটি

অ্যামোর্টাইজড অ্যানালিসিস

এই অ্যানালিসিস তখন ব্যবহৃত হয় যখন কখনো কখনো অপারেশন খুব স্লো হয়, কিন্তু অধিকাংশ অপারেশন যা খুব ঘন ঘন এক্সিকিউট হয় সেগুলো ফাস্ট হয়। ডেটা স্ট্রাকচারে হ্যাশ টেবল, ডিসজয়েন্ট সেট ইত্যাদির জন্য অ্যামোর্টাইজড অ্যানালيسিস দরকার।

হ্যাশ-টেবিলে, অধিকাংশ সময় সার্চিং টাইম কমপ্লেক্সিটি O(1), কিন্তু কখনো কখনো এটি O(n) অপারেশন এক্সিকিউট করে। যখন আমরা হ্যাশ টেবিলে কোনো এলিমেন্ট সার্চ বা ইনসার্ট করতে চাই, অধিকাংশ কেসে এটি কনস্ট্যান্ট টাইম নেয়, কিন্তু колиশন হলে কলিশন রেজোলিউশনের জন্য O(n) টাইম লাগে।

এগ্রিগেট মেথড

এগ্রিগেট মেথড টোটাল কস্ট বের করতে ব্যবহৃত হয়। যদি আমরা অনেক ডেটা যোগ করতে চাই, তবে অ্যামোর্টাইজড কস্ট এই সূত্র দিয়ে বের করতে হয়।

n অপারেশনের একটি সিকোয়েন্সের জন্য, খরচ হল -

$\frac{Cost ( n\:operations)}{n}=\frac{Cost (normal\:operations)+Cost (Expensive\:operations)}{n}$

অ্যামোর্টাইজড অ্যানালিসিসের উদাহরণ

একটি ডাইনামিক অ্যারেতে, আইটেমগুলো একটি দিয়ে যেওয়া ইন্ডেক্সে O(1) টাইমে ইনসার্ট করা যায়। কিন্তু যদি সেই ইন্ডেক্স অ্যারেতে নেই, তবে কনস্ট্যান্ট টাইমে টাস্ক পারফর্ম করতে ব্যর্থ হয়। সেক্ষেত্রে, এটি প্রাথমিকভাবে অ্যারের সাইজ ডাবল করে তারপর এলিমেন্ট ইনসার্ট করে যদি ইন্ডেক্স উপস্থিত থাকে।

ডাইনামিক অ্যারেতে, cᵢ = i-তম ইনসারশনের কস্ট।

$So\:c_i=1+\begin{cases}i-1, if\: i-1\: is\: power\: of\: 2 \\ 0, \: otherwise \end{cases}$

$$\frac{\sum_{i=1}^n c_i}{n} \leq \frac{n + \sum_{j=1}^{\lfloor\log_{2}(n-1)\rfloor} 2^j}{n} = \frac{O(n)}{n}$$