পটেনশিয়াল মেথড

১ · পটেনশিয়াল ফাংশন — সঞ্চিত "শক্তি" পরিমাপ

পটেনশিয়াল মেথড পদার্থবিজ্ঞানের পটেনশিয়াল এনার্জির ধারণা থেকে অনুপ্রাণিত। ডেটা স্ট্রাকচারের প্রতিটি অবস্থার (state) জন্য একটি সংখ্যা $\Phi(\text{state})$ সংজ্ঞায়িত করা হয় — এটি বোঝায় সেই মুহূর্তে ডেটা স্ট্রাকচারে কতটা "সঞ্চিত potential" আছে, যা ভবিষ্যতের একটি ব্যয়বহুল অপারেশনের cost "প্রি-পেইড" (আগে থেকে পরিশোধ করা) হিসেবে কাজ করতে পারে। $i$-তম অপারেশনের amortized cost সংজ্ঞায়িত হয়:

$$\hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) = c_i + \Delta\Phi_i$$

এখানে $c_i$ হলো actual cost, $D_{i-1}$ ও $D_i$ হলো অপারেশনের আগে ও পরের ডেটা স্ট্রাকচারের অবস্থা। $n$-টি অপারেশনের মোট amortized cost যোগ করলে (টেলিস্কোপিং সাম — মাঝের সব $\Phi$ মান বাতিল হয়ে যায়):

$$\sum_{i=1}^{n} \hat{c}_i = \sum_{i=1}^{n} c_i + \Phi(D_n) - \Phi(D_0)$$

যদি $\Phi(D_0) = 0$ (শুরুতে) এবং $\Phi(D_i) \ge 0$ সবসময় (কোনো অবস্থাতেই ঋণাত্মক নয়), তাহলে $\sum c_i \le \sum \hat{c}_i$ — অর্থাৎ, amortized cost-এর যোগফল প্রকৃত cost-এর যোগফলের একটি বৈধ upper bound। এটাই মূল কৌশল: প্রতিটি $\hat{c}_i$ ধ্রুবক ($O(1)$) প্রমাণ করতে পারলেই মোট প্রকৃত cost $O(n)$।

২ · একই ডাইনামিক অ্যারে-তে $\Phi$ নির্বাচন

L43/L44-এর সেই একই ক্যাপাসিটি-ডাবলিং ডাইনামিক অ্যারের জন্য নেওয়া যাক:

$$\Phi(\text{size}, \text{capacity}) = 2 \cdot \text{size} - \text{capacity}$$

এটি একটি বৈধ পটেনশিয়াল ফাংশন হওয়ার জন্য দুটো শর্ত পূরণ করতে হবে: (ক) ফাঁকা অ্যারেতে ($\text{size}=0, \text{capacity}=0$) $\Phi = 0$ — সত্যি, কারণ $2 \times 0 - 0 = 0$। (খ) সবসময় $\Phi \ge 0$ — এটি সত্য কারণ এই ডিজাইনে ক্যাপাসিটি রিয়েলোকেশনের ঠিক পরপরই $\text{capacity} = 2 \times \text{size}_{\text{old}}$ এবং নতুন $\text{size} = \text{size}_{\text{old}} + 1$, তাই $\Phi = 2(\text{size}_{\text{old}}+1) - 2\,\text{size}_{\text{old}} = 2 > 0$; আর দুটো রিয়েলোকেশনের মাঝামাঝি সময়ে $\text{size}$ ক্যাপাসিটির অর্ধেকের বেশি থাকে (কারণ শেষ রিয়েলোকেশনে ঠিক অর্ধেক ভরাট অবস্থায় ছিল), তাই $2\,\text{size} \ge \text{capacity}$।

এবার দুই ধরনের push-এ amortized cost হিসাব করা যাক:

সাধারণ push (রিয়েলোকেশন ছাড়া): size $s \to s+1$, capacity $c$ অপরিবর্তিত। actual cost $c_i = 1$।

$$\Delta\Phi = \big(2(s+1) - c\big) - (2s - c) = 2 \quad\Rightarrow\quad \hat{c}_i = 1 + 2 = 3$$

রিয়েলোকেশন push: size $s = c$ (পূর্ণ) $\to$ নতুন capacity $c' = 2c$, নতুন size $s+1$। actual cost $c_i = s + 1$ (কপি $s$টি + অ্যাসাইনমেন্ট $1$)।

$$\Delta\Phi = \big(2(s+1) - 2c\big) - (2s - c) = 2 - c = 2 - s \quad\Rightarrow\quad \hat{c}_i = (s+1) + (2-s) = 3$$

দুই ক্ষেত্রেই amortized cost ঠিক $3$! (প্রথম push-টি একটি বিশেষ প্রান্তিক ঘটনা — $\text{capacity}=0$ থেকে $1$-এ যাওয়ার সময় সূত্রে সামান্য পার্থক্য আসে, amortized cost হয় $2$, তাও $3$-এর মধ্যেই বাউন্ডেড)। এটাই পটেনশিয়াল মেথডের শক্তি — এটি প্রতিটি push-এর amortized cost একটি নির্দিষ্ট সূত্র দিয়ে বের করে দেয়, L44-এর মতো charge "অনুমান করে বসিয়ে" পরীক্ষা করতে হয় না।

class DynamicArray:
    """L43/L44-এর হুবহু একই ক্যাপাসিটি-ডাবলিং ডাইনামিক অ্যারে।"""

    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 phi(size, capacity):
    """পটেনশিয়াল ফাংশন: Phi = 2*size - capacity"""
    return 2 * size - capacity


n = 2000
da = DynamicArray()
amortized_costs = []
phi_prev = phi(da.size, da.capacity)  # শুরুতে size=0, capacity=0 -> Phi = 0

min_phi_seen = phi_prev

for i in range(n):
    actual_cost = da.push(i)
    phi_new = phi(da.size, da.capacity)
    delta_phi = phi_new - phi_prev
    amortized = actual_cost + delta_phi
    amortized_costs.append(amortized)

    assert phi_new >= 0, f"push #{i+1}-এ Phi ঋণাত্মক হয়ে গেছে: {phi_new}"
    assert amortized <= 3, f"push #{i+1}-এ amortized cost 3-এর বেশি: {amortized}"

    min_phi_seen = min(min_phi_seen, phi_new)
    phi_prev = phi_new

print(f"{n}টি push-এর উপর পটেনশিয়াল মেথড যাচাই")
print(f"amortized cost-এর সর্বনিম্ন মান: {min(amortized_costs)}")
print(f"amortized cost-এর সর্বোচ্চ মান: {max(amortized_costs)}")
print(f"সব amortized cost কি <= 3? {all(c <= 3 for c in amortized_costs)}")
print(f"পুরো রানে সর্বনিম্ন Phi মান (কখনও ঋণাত্মক হয়নি): {min_phi_seen}")
print(f"গড় amortized cost: {sum(amortized_costs) / n:.4f}")
print(f"\nপ্রথম ১২টি push-এর amortized cost: {amortized_costs[:12]}")