Amortized analysis là gì, dùng việc resize dynamic array làm ví dụ?

Question

Accepted Answer

**Amortized analysis** (phân tích khấu hao) đo **chi phí trung bình mỗi thao tác trên một chuỗi (sequence)**, ngay cả khi các thao tác riêng lẻ thỉnh thoảng tốn nhiều hơn nhiều. Nó giải thích tại sao `append` của một dynamic array là "**O(1) amortized**" mặc dù thỉnh thoảng có các lần resize O(n).

## Ví dụ dynamic array

Khi một dynamic array đầy, nó cấp phát một array mới (thường **2×**) và sao chép tất cả phần tử — một bước O(n). Nhưng vì dung lượng **nhân đôi**, các lần sao chép tốn kém trở nên hiếm hơn theo cấp số nhân.

```text
Append vào một array nhân đôi (cap được hiển thị):
ops:   1  2  3  4  5  6  7  8  9
cap:   1  2  4  4  8  8  8  8  16
copy:  *  *  *     *           *      <- sao chép tại 1,2,4,8,16...
```

## Phép toán

```text
Để chèn n phần tử, tổng công sao chép =
  1 + 2 + 4 + ... + n  ≈  2n   (cấp số nhân)
Tổng chi phí cho n lần chèn = O(n)
Chi phí amortized mỗi lần chèn = O(n)/n = O(1)
```

```python
arr = []
for i in range(1_000_000):
    arr.append(i)   # hầu như luôn O(1); hiếm khi O(n) trong lúc resize
```

| Thao tác | Một lần tệ nhất | Amortized |
|---|---|---|
| append (nhân đôi) | O(n) | **O(1)** |

## Tại sao nhân đôi (chứ không phải +1)

Phát triển theo một **lượng hằng số** sẽ khiến mỗi lần chèn kích hoạt một lần sao chép, cho amortized O(n). Phát triển theo cấp số nhân là cái dàn trải chi phí ra.

## Tại sao điều này quan trọng

Amortized analysis cho một bức tranh hiệu năng công bằng, thực tế — không có nó, bạn sẽ lo sai rằng mỗi `append` hoặc chèn hash-table là O(n).

Nó cũng biện minh cho một quy tắc thiết kế then chốt: **phát triển dung lượng theo cấp số nhân**, điều nằm dưới dynamic array, hash table, và string builder ở khắp nơi.