Amortized analysis คืออะไร โดยใช้ dynamic array resizing เป็นตัวอย่าง?

Question

Accepted Answer

**Amortized analysis** วัด **ต้นทุนเฉลี่ยต่อการดำเนินการในลำดับ** แม้ว่าการดำเนินการแต่ละรายการบางครั้งจะมีต้นทุนสูงกว่ามาก มันอธิบายว่าทำไม `append` ของ dynamic array จึงเป็น "**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 แต่ละครั้งเรียก copy ส่งผลให้ O(n) amortized การเพิ่มแบบทวีคูณคือสิ่งที่กระจายต้นทุน

## เหตุใดจึงสำคัญ

Amortized analysis ให้ภาพที่ยุติธรรมและสมจริงของประสิทธิภาพ — หากไม่มี คุณจะกลัวอย่างผิดพลาดว่าทุก `append` หรือ insert ในตาราง hash นั้น O(n)

นอกจากนี้ยังสนับสนุนกฎการออกแบบที่สำคัญ: **การเพิ่มความจุแบบทวีคูณ** ซึ่งเป็นพื้นฐานของ dynamic arrays ตาราง hash และ string builders ทั่วไป