অ্যাকাউন্টিং মেথড

১ · অ্যাকাউন্টিং মেথডের ধারণা

L43-এ আমরা অ্যাগ্রিগেট মেথড দিয়ে দেখিয়েছি $n$-টি push-এর মোট cost $< 3n$, তাই amortized cost per push $O(1)$। অ্যাকাউন্টিং মেথড একই সিদ্ধান্তে পৌঁছায়, কিন্তু ভিন্নভাবে — প্রতিটি অপারেশনের জন্য একটি নির্দিষ্ট amortized chargeAmortized Chargeপ্রতিটি অপারেশনে "ধার্যকৃত" একটি কৃত্রিম, ধ্রুবক cost — বাস্তব cost-এর সমান হতে হবে না, শুধু এটা প্রমাণ করতে হবে যে সমস্ত অপারেশনের মোট charge সবসময় মোট প্রকৃত cost-এর চেয়ে বেশি বা সমান থাকে। নির্ধারণ করে। যদি কোনো অপারেশনের প্রকৃত cost তার charge-এর চেয়ে কম হয়, উদ্বৃত্ত অংশ credit হিসেবে জমা থাকে। যখন কোনো অপারেশনের প্রকৃত cost তার charge-এর চেয়ে বেশি হয় (যেমন রিয়েলোকেশন), জমা করা credit থেকে সেই ঘাটতি মেটানো হয়।

$$\text{credit balance after operation } i = \sum_{j=1}^{i} \left(\text{charge}_j - \text{actual\_cost}_j\right)$$

পুরো প্রমাণ দাঁড়িয়ে থাকে একটি শর্তের উপর: credit balance কখনও ঋণাত্মক হতে পারবে না — কারণ ঋণাত্মক credit মানে আমরা এমন cost মেটাচ্ছি যা এখনও charge করাই হয়নি, যা বৈধ নয়। যদি এই ইনভেরিয়েন্ট সবসময় বজায় থাকে, তাহলে মোট charge $\ge$ মোট actual cost — এবং যেহেতু charge একটি ধ্রুবক ($3$), তাই মোট actual cost $\le 3n = O(n)$, অর্থাৎ amortized cost per push $O(1)$।

২ · একই ডাইনামিক অ্যারে, charge $= 3$ কেন

L43-এর সেই একই ক্যাপাসিটি-ডাবলিং ডাইনামিক অ্যারে নেওয়া যাক। প্রতিটি push-কে charge করা হবে $3$ ইউনিট: $1$ ইউনিট আসল অ্যাসাইনমেন্টের জন্য ব্যয় হয়, বাকি $2$ ইউনিট credit হিসেবে জমা রাখা হয়। দাবি: যখনই অ্যারে পূর্ণ হয়ে রিয়েলোকেশন ঘটে (আকার $s$-এ, যেখানে $s$ বর্তমান ক্যাপাসিটির সমান), জমাকৃত credit ঠিক সেই মুহূর্তে $s$টি এলিমেন্ট কপি করার cost মেটাতে যথেষ্ট।

কেন? শেষ রিয়েলোকেশনের পর থেকে (যখন ক্যাপাসিটি $s/2$ থেকে $s$-এ দ্বিগুণ হয়েছিল) ঠিক $s/2$টি push হয়েছে (আকার $s/2$ থেকে $s$ পর্যন্ত পৌঁছাতে)। প্রতিটি push $2$ ইউনিট credit জমা করেছে, তাই মোট জমাকৃত credit $= 2 \times (s/2) = s$ — যা ঠিক পরবর্তী রিয়েলোকেশনের কপি-cost ($s$টি এলিমেন্ট)-এর সমান। credit ঠিক পুরোটাই খরচ হয়ে যায়, কখনও ঋণাত্মক হয় না:

$$\underbrace{2 \times \frac{s}{2}}_{\text{জমাকৃত credit}} = \underbrace{s}_{\text{রিয়েলোকেশন কপি cost}}$$

লক্ষ্য করুন এই বীজগণিতটাই L43-এর অ্যাগ্রিগেট মেথডের জ্যামিতিক সিরিজের যুক্তির সাথে সরাসরি সংযুক্ত — সেখানে মোট কপি cost $< 2n$ ছিল বলেই এখানে "$2$ ইউনিট credit প্রতি push" নির্বাচন করাটা ঠিক কাজ করে। যদি charge $3$-এর বদলে $2$ ধরা হতো (অর্থাৎ push প্রতি মাত্র $1$ ইউনিট credit), credit যথেষ্ট হতো না — নিচের কোড সেলে এটি সত্যিই ভেঙে পড়তে দেখা যাবে।

class DynamicArray:
    """L43-এর হুবহু একই ক্যাপাসিটি-ডাবলিং ডাইনামিক অ্যারে -- আসল (actual) cost
    ফেরত দেয় প্রতিটি push()-এ, যাতে amortized charge-এর সাথে তুলনা করা যায়।"""

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

    def push(self, value):
        cost = 0
        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


def run_with_charge(n, charge):
    """charge ইউনিট প্রতি push ধার্য করে, credit balance ট্র্যাক করে।
    যদি কোনো মুহূর্তে balance ঋণাত্মক হয়ে যায় -- AssertionError তোলে।"""
    da = DynamicArray()
    credit = 0
    min_credit = None
    for i in range(1, n + 1):
        actual_cost = da.push(i)
        credit += charge - actual_cost
        if min_credit is None or credit < min_credit:
            min_credit = credit
        assert credit >= 0, f"push #{i}-এ credit ঋণাত্মক হয়ে গেছে: {credit}"
    return credit, min_credit


n = 2000

final_credit, min_credit = run_with_charge(n, charge=3)
print(f"charge = 3 ইউনিট/push দিয়ে {n}টি push চালানো হলো")
print(f"শেষে জমাকৃত credit: {final_credit}")
print(f"পুরো সিকোয়েন্সে সর্বনিম্ন credit balance: {min_credit}")
print("--> কখনও ঋণাত্মক হয়নি, তাই charge = 3 বৈধ।\n")

print("এবার charge = 2 দিয়ে চেষ্টা করা যাক (L43-এর অ্যাগ্রিগেট প্রমাণ অনুযায়ী এটি যথেষ্ট নয়):")
try:
    run_with_charge(n, charge=2)
    print("charge = 2 ব্যর্থ হয়নি -- এটা প্রত্যাশিত ছিল না!")
except AssertionError as e:
    print(f"প্রত্যাশিতভাবেই ব্যর্থ: {e}")