Amortized பகுப்பாய்வு என்றால் என்ன, dynamic array resizing-ஐ எடுத்துக்காட்டாக பயன்படுத்தி?

Question

Accepted Answer

**Amortized பகுப்பாய்வு** ஒரு வரிசையில் **இயக்கத்திற்கு சராசரி செலவை** அளவிடுகிறது, தனிப்பட்ட இயக்கங்கள் சில சமயங்களில் மிக அதிகமாக செலவாகினாலும் கூட. இது ஏன் ஒரு dynamic array-ன் `append` "**O(1) amortized**" என்பதை விளக்குகிறது, கருதினும் O(n) resizes அவ்வப்போது நடக்கின்றன.

## Dynamic array எடுத்துக்காட்டு

ஒரு dynamic array நிரம்பும்போது, அது ஒரு புதிய array (பொதுவாக **2×**) ஒதுக்குகிறது மற்றும் அனைத்து உறுப்புகளையும் நகலெடுக்கிறது — O(n) படி. ஆனால் திறன் **இரட்டிப்பாகிறது** என்பதால், விலையுயர்ந்த நகলெடுப்பு அதிவேகமாக அரிதாகி விடுகிறது.

```text
Appending into a doubling array (cap shown):
ops:   1  2  3  4  5  6  7  8  9
cap:   1  2  4  4  8  8  8  8  16
copy:  *  *  *     *           *      <- copies at 1,2,4,8,16...
```

## கணிதம்

```text
To insert n elements, total copy work =
  1 + 2 + 4 + ... + n  ≈  2n   (geometric series)
Total cost for n inserts = O(n)
Amortized cost per insert = O(n)/n = O(1)
```

```python
arr = []
for i in range(1_000_000):
    arr.append(i)   # almost always O(1); rarely O(n) during a resize
```

| இயக்கம் | மோசமான ஒற்றை | Amortized |
|---|---|---|
| append (இரட்டிப்பாக்குதல்) | O(n) | **O(1)** |

## ஏன் இரட்டிப்பாக்குதல் (+1 அல்ல)

**மாறிலி** தொகையால் வளர்தல் ஒவ்வொரு insert ஐ ஒரு நகலெடுப்புக்கு ஏற்படுத்தும், O(n) amortized ஐ கொடுக்கும். பெருக்கல் வளர்ச்சி செலவை வெளியே பரப்புவது.

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

Amortized பகுப்பாய்வு நியாயமான, யাதார்த்யமான செயல்திறனின் படத்தை அளிக்கிறது — அதில்லாமல், ஒவ்வொரு `append` அல்லது hash-table insert ஆக O(n) என்று தவறுதலாக பயப்பீர்கள்.

இது ஒரு முக்கிய வடிவமைப்பு விதியையும் நியாயப்படுத்துகிறது: **திறன் பெருக்கல் வளர்ச்சி**, இது dynamic arrays, hash tables, மற்றும் string builders எங்கும் அடிப்படை.