Amortized Analysis — மாணவர்களுக்கு எளிய விளக்கம் மற்றும் Python உதாரணங்கள்

ஏன் இது முக்கியம்?

Python list-க்கு append O(1) amortized என்று சொன்னால் அர்த்தம்:

• பெரும்பாலான append மிகவும் வேகமான வேலை.
• சில நேரங்களில் ஒரு append செலவு அதிகம் — list grow ஆகி, memory-ல் elements copy செய்ய வேண்டும்.
• அந்த அரிதான “பெரிய செலவு”-ஐ பல சிறிய append-கள் மீது பரப்பினால், நீண்ட காலத்தில் ஒரு append-க்கு சராசரி O(1) போலத் தோன்றும்.

இந்த “நீண்ட கால சராசரி” யோசனைதான் amortized analysis.

---

Worst case vs amortized (காபி கடை உவமை)

காபி stamp card: 9 காபி வாங்கினால் 10வது free.

• 10வது visit-ல் reward — அன்று “பெரிய லாபி” போலத் தோன்றும்.
• 10 visit-க்கு நீங்கள் 9 காபிக்கு பணம் கொடுத்து 10 serving.

ஒரு காபிக்கு சராசரி செலவு குறைவு.

Amortized பார்வை: ஒரு “செலவு அதிகமான” நிகழ்வு, அதற்கு முன் வந்த பல சிறிய visit-களால் பணம் செலுத்தப்பட்டது போல.

Algorithms-ல் ஒரு slow operation-க்கு முன் வந்த பல வேகமான operations “பில்” செலுத்துகின்றன.

---

Aggregate method (n operations: மொத்தம் ÷ n)

மாணவர்கள் பயன்படுத்தும் எளிய வழி:

1. n operations (உதாரணம்: n append) ஓடவிடுங்கள்.
2. மொத்த உண்மையான வேலை (copy / basic steps) கூட்டுங்கள்.
3. n-ஆல் வகுக்கவும் → ஒரு operation-க்கு சராசரி.

அந்த சராசரி O(1) என்றால், ஒவ்வொரு operation-யும் O(1) amortized என்கிறோம்.

இது ஒவ்வொரு step-யும் worst-case O(1) என்று சொல்லாது — பல step-களின் சராசரி constant என்று சொல்கிறது.

---

உதாரணம் 1 — Dynamic array: capacity இரட்டிப்பு

பல மொழிகள் array நிரம்பினால் இரட்டிப்பு size-க்கு grow செய்கின்றன. resize-க்குப் பிறகு, அடுத்த resize வரை பல cheap append இடம் உள்ளது.

class GrowableArray:
    """Toy model: Python list-அளவு வேகமல்ல; idea-க்கு."""

    def __init__(self):
        self._data = [None] * 1
        self._size = 0

    def __len__(self):
        return self._size

    def append(self, value: int) -> None:
        if self._size == len(self._data):
            self._resize()
        self._data[self._size] = value
        self._size += 1

    def _resize(self) -> None:
        old = self._data
        new_cap = max(1, len(old) * 2)
        self._data = [None] * new_cap
        for i in range(self._size):
            self._data[i] = old[i]


def total_append_steps(n: int) -> int:
    a = GrowableArray()
    steps = 0
    for k in range(n):
        before = len(a._data)
        if a._size == before:
            steps += a._size
        a.append(k)
        steps += 1
    return steps


for n in (10, 100, 1000):
    s = total_append_steps(n)
    print(n, "appends ->", s, "steps, average", s / n)

எண்களைப் பாருங்கள்: மொத்த steps O(n) — ஒரு append-க்கு சராசரி constant — அதுதான் O(1) amortized append.

---

உதாரணம் 2 — Binary counter (increment amortized O(1))

Binary எண்ணை ஒன்று கூட்டும்போது பல bit மாறலாம் (எல்லா 1-யும் roll over) — ஆனால் அந்த “நீண்ட carry” அரிது.

def increment(bits: list[int]) -> int:
    """bits[0] LSB. எத்தனை bit flip என்று return."""
    flips = 0
    i = 0
    while i < len(bits) and bits[i] == 1:
        bits[i] = 0
        flips += 1
        i += 1
    if i < len(bits):
        bits[i] = 1
        flips += 1
    else:
        bits.append(1)
        flips += 1
    return flips


def run_counter(n: int) -> None:
    bits = [0]
    total_flips = 0
    for step in range(n):
        f = increment(bits)
        total_flips += f
    print(n, "increments ->", total_flips, "flips, average", total_flips / n)


run_counter(256)

Intuition: ஒரு bit 0→1 ஆகும்போது “செலுத்துகிறோம்”; 1→0 reset முன்பு செலுத்தியதன் பங்கு. பல increment-க்கு மொத்த flips ≈ O(n) → ஒரு increment-க்கு amortized O(1).

---

உதாரணம் 3 — Stack மற்றும் multipop (optional)

சில API-களில் ஒரு call expensive ஆக இருக்கலாம், ஆனால் அது நீக்கும் items push செய்தபோது ஏற்கனவே செலுத்தப்பட்ட “வேலை” போல.

class Stack:
    def __init__(self):
        self._items: list[int] = []

    def push(self, x: int) -> None:
        self._items.append(x)

    def multipop(self, k: int) -> int:
        count = 0
        while self._items and count < k:
            self._items.pop()
            count += 1
        return count

n push + multipop கலவை: மொத்த pop எண்ணிக்கை push எண்ணிக்கையை விட அதிகமாகாது — aggregate style argument.

---

Amortized analysis என்ன இல்லை

• Average case (random input probability) அல்ல.
• Worst case-ஐ மறைக்காது — sequence of operations-க்கு உண்மையான செலவு.

---

Interview-ல் எப்படி சொல்வது (மாணவர் பதிப்பு)

“சில operations அரிதாக பெரிய bill செலுத்தும். அந்த bill, கடைசி bill-க்குப் பிறகு வந்த பல cheap operations-உடன் grow ஆனால், ஒரு cheap operation-க்கு சராசரி constant share — அதனால் amortized O(1).”

---

முக்கிய புள்ளிகள்

• Amortized = அரிதான expensive step-ஐ பல cheap steps மீது பரப்புதல்.
• Dynamic arrays doubling → resize அரிது → O(1) amortized append.
• Binary counter → O(1) amortized increment.
• தொடக்கத்தில் aggregate method: n operations-க்கு மொத்த செலவு ÷ n.

---

சிறு பயிற்சி (Python)

1. n = 1_000_000க்கு எத்தனை resize நிகழ்வுகள் (சுமார் log₂(n)).
2. Binary counter-ல் run_counter(10_000) ஓடி, step-க்கு சராசரி flip சிறியதாக இருப்பதைப் பாருங்கள்.

இதில் வசதி பெற்ற பிறகு, ஒரு operation-க்கு worst-case complexity மற்றும் sequence-க்கு amortized guarantee — இந்த வேறுபாடு interview-ல் மதிப்பு கூட்டும்.