অ্যামর্টাইজড অ্যানালাইসিস — অ্যাগ্রিগেট মেথড

১ · সমস্যাটা কী — worst-case-প্রতি-অপারেশন কেন যথেষ্ট নয়

ধরুন একটি ডেটা স্ট্রাকচারে $n$-টি অপারেশন করা হবে, এবং প্রতিটি অপারেশনের worst-case cost $O(n)$। সরল যুক্তিতে মনে হতে পারে পুরো সিকোয়েন্সের cost $O(n) \times n = O(n^2)$। কিন্তু বাস্তবে অনেক ডেটা স্ট্রাকচারে এই "ব্যয়বহুল" ঘটনাটি প্রায়ই ঘটে না — এটি ঘটার পর পরবর্তী অনেকগুলো অপারেশন সস্তা হতে বাধ্য হয়। এই নির্ভরতা ধরতে না পারলে অ্যানালাইসিস অপ্রয়োজনীয়ভাবে লুজ (pessimistic) হয়ে যায়।

অ্যামর্টাইজড অ্যানালাইসিসAmortized Analysisএকটি ডেটা স্ট্রাকচারের উপর করা অপারেশনগুলোর একটি সম্পূর্ণ সিকোয়েন্সের মোট cost বিশ্লেষণ করে প্রতি-অপারেশন গড় cost বের করার কৌশল — এলোমেলো ইনপুটের উপর নির্ভরশীল average-case অ্যানালাইসিসের (L08) থেকে আলাদা, কারণ এটি guaranteed (worst-case সিকোয়েন্সেও সত্য), র‍্যান্ডম বা প্রায়োগিক ধারণার উপর নয়। সমাধান দেয় — এটি বলে না "গড় ইনপুটে" cost কম, বরং প্রমাণ করে যে যেকোনো সিকোয়েন্সে মোট cost সবসময় একটি নির্দিষ্ট বাউন্ডের মধ্যে থাকবেই। তিনটি প্রমাণ কৌশল আছে — অ্যাগ্রিগেট মেথড (এই পাঠ), অ্যাকাউন্টিং মেথড (L44), এবং পটেনশিয়াল মেথড (L45)। তিনটিই একই সিদ্ধান্তে পৌঁছায়, শুধু ভিন্ন উপায়ে প্রমাণ করে।

২ · ক্যাপাসিটি-ডাবলিং ডাইনামিক অ্যারে

একটি ডাইনামিক অ্যারে একটি ফিক্সড-সাইজ capacity নিয়ে শুরু হয়। যতক্ষণ জায়গা আছে, push() শুধু পরবর্তী খালি স্লটে মান বসায় — cost $1$। কিন্তু যখন অ্যারে পূর্ণ হয়ে যায় (size == capacity), তখন একটি নতুন, দ্বিগুণ ক্যাপাসিটির অ্যারে বরাদ্দ করে পুরনো সব এলিমেন্ট নতুন অ্যারেতে কপি করতে হয় — cost $= \text{size} + 1$ (পুরনো এলিমেন্ট কপি + নতুন এলিমেন্ট বসানো)।

৩ · অ্যাগ্রিগেট মেথড — মোট cost সরাসরি গণনা

ধরা যাক ফাঁকা অ্যারে থেকে শুরু করে $n$-টি push() করা হলো। প্রতিটি push-এ নতুন এলিমেন্ট বসানোর জন্য cost $1$ — মোট $n$। এছাড়া, প্রতিবার রিয়েলোকেশন ঘটলে অতিরিক্ত কপি cost লাগে। ক্যাপাসিটি যায় $1, 2, 4, \dots, 2^{k-1}$ পর্যন্ত (যেখানে $2^{k-1} < n$), এবং প্রতিটি রিয়েলোকেশনে কপি cost পুরনো ক্যাপাসিটির সমান:

$$\text{মোট কপি cost} = \sum_{i=0}^{k-1} 2^i = 2^k - 1 < 2n$$

(কারণ $2^{k-1} < n$ মানে $2^k < 2n$)। সুতরাং:

$$\text{মোট cost} = \underbrace{n}_{\text{প্রতিটি push-এর অ্যাসাইনমেন্ট}} + \underbrace{(2^k - 1)}_{\text{সব রিয়েলোকেশনের কপি}} < n + 2n = 3n$$

$$\text{Amortized cost per push} = \frac{\text{মোট cost}}{n} < 3 = O(1)$$

এখানেই অ্যাগ্রিগেট মেথডের মূল কৌশল — প্রতিটি অপারেশন আলাদাভাবে না দেখে পুরো সিকোয়েন্সের মোট cost সরাসরি গণনা করে, তারপর $n$ দিয়ে ভাগ করে amortized cost বের করা হয়। কেন এটি কাজ করে তা বোঝার চাবিকাঠি হলো: ক্যাপাসিটি দ্বিগুণ (গুণিতক হারে) বাড়ে বলেই কপি cost-গুলো একটি জ্যামিতিক সিরিজ তৈরি করে, যার যোগফল রৈখিক ($O(n)$) — যদি ক্যাপাসিটি প্রতিবার মাত্র $1$ করে বাড়ানো হতো (গাণিতিক সিরিজ), যোগফল হতো $O(n^2)$, এবং amortized cost হতো $O(n)$, একদমই $O(1)$ নয়।

class DynamicArray:
    """ফাঁকা অবস্থা থেকে শুরু হয়ে, ভর্তি হয়ে গেলে ক্যাপাসিটি ডাবল করে
    পুরনো এলিমেন্টগুলো নতুন অ্যারেতে কপি করে -- ক্লাসিক ডাইনামিক অ্যারে।"""

    def __init__(self):
        self.capacity = 0
        self.size = 0
        self.arr = []

    def push(self, value):
        cost = 0  # এই push()-এ মোট কতগুলো "বেসিক অপারেশন" (কপি + অ্যাসাইনমেন্ট) হলো
        if self.size == self.capacity:
            # অ্যারে পূর্ণ -- রিয়েলোকেট করে ক্যাপাসিটি ডাবল করা হচ্ছে
            new_capacity = 1 if self.capacity == 0 else self.capacity * 2
            new_arr = [None] * new_capacity
            for i in range(self.size):
                new_arr[i] = self.arr[i]
                cost += 1          # প্রতিটি কপি একটি অপারেশন
            self.arr = new_arr
            self.capacity = new_capacity
        self.arr[self.size] = value
        self.size += 1
        cost += 1                  # নতুন এলিমেন্ট বসানো
        return cost


n = 2000
da = DynamicArray()
total_copies = 0
total_cost = 0
per_push_cost = []

for i in range(n):
    c = da.push(i)
    per_push_cost.append(c)
    total_cost += c
    total_copies += (c - 1)   # cost থেকে ১ (অ্যাসাইনমেন্ট) বাদ দিলে বাকিটাই কপি

print(f"মোট push সংখ্যা (n): {n}")
print(f"মোট কপি অপারেশন: {total_copies}")
print(f"মোট কপি / n: {total_copies / n:.4f}")
print(f"মোট cost (কপি + অ্যাসাইনমেন্ট): {total_cost}")
print(f"গড় (amortized) cost per push = মোট cost / n: {total_cost / n:.4f}")

print("\nসবচেয়ে ব্যয়বহুল ১০টি push (বাকি প্রায় সবগুলোরই cost = 1):")
top10 = sorted(range(1, n + 1), key=lambda i: -per_push_cost[i - 1])[:10]
for idx in sorted(top10):
    print(f"  push #{idx}: cost = {per_push_cost[idx - 1]}")