Chuyển tới nội dung chính

Phân tích amortized (khấu hao)

Bạn sẽ học được gì

Một thao tác có thể thỉnh thoảng rất đắt nhưng nếu tính trung bình trên nhiều lần thì lại rẻ. Đó là phân tích amortized (khấu hao). Bài này (nâng cao) dùng ví dụ kinh điển: thêm phần tử vào mảng động.

1. Trực quan: tiền thuê nhà trả theo năm​

Bạn trả tiền nhà 12 triệu một lần mỗi năm. Tháng đó nhìn rất "đắt". Nhưng nếu chia đều ra, chỉ 1 triệu/tháng — rẻ và đều. Amortized chính là cách nhìn "chia đều chi phí của cú đắt hiếm hoi ra cho nhiều lần rẻ".

Phân biệt với xấu nhất: xấu nhất nói "có lần tốn 12 triệu!"; amortized nói "trung bình mỗi tháng chỉ 1 triệu". Cả hai đều đúng, nhưng amortized phản ánh chi phí thật khi làm nhiều lần.

2. Bài toán: thêm phần tử vào mảng động​

Mảng trong Python (list), Java (ArrayList)... là mảng động: tự lớn lên khi đầy. Cách hoạt động bên trong:

  • Mảng có sức chứa (capacity) cố định.
  • Thêm phần tử khi còn chỗ → chỉ ghi 1 ô → O(1), rẻ.
  • Thêm khi đã đầy → phải xin vùng nhớ mới lớn gấp đôi, copy toàn bộ sang → tốn O(size), đắt!

Vậy thêm 1 phần tử là O(1) hay O(n)? Câu trả lời: xấu nhất một lần là O(n), nhưng amortized là O(1).

3. Chạy debug: khoảnh khắc nhân đôi​

Bước qua vài lần thêm. Để ý cap (sức chứa) nhân đôi khi đầy, và chi_phi lần đó vọt lên:

🐞 Thêm phần tử vào mảng độngBước 1/9
1def them(x):
2  if size == cap:        # day -> phai mo rong
3      cap = cap * 2      # nhan doi suc chua
4      copy_tat_ca()      # copy het: ton O(size)
5  arr[size] = x          # ghi phan tu moi: O(1)
6  size = size + 1
Biến tại bước này
size0
cap1
👉 Thêm phần tử 1: 0 == 1? Chưa đầy.

4. Nhìn tận mắt: trung bình hội tụ về hằng số​

Bấm Run — cột trung_binh (tổng chi phí / số phần tử) không phình theo n, nó dừng quanh ~2-3:

Đang tải trình chạy code…

Dù vài lần chi phí vọt lên (9, 17...), trung bình mỗi lần thêm vẫn là hằng số vì các cú nhân đôi ngày càng thưa (cách nhau gấp đôi mỗi lần). Đó là vì sao ta nói list.append là amortized O(1).

5. Vì sao "nhân đôi" mà không "cộng thêm 1 chỗ"?​

Nếu mỗi lần đầy chỉ mở rộng thêm 1 ô, thì lần nào cũng phải copy → tổng O(n²), tệ. Nhân đôi làm số lần copy ít đi theo cấp số nhân → tổng chi phí O(n) cho n lần thêm → trung bình O(1). Một lựa chọn thiết kế nhỏ mà thay đổi cả độ phức tạp.

6. Mẫu nhận diện​

  • Thao tác thường rẻ, thỉnh thoảng đắt, và cú đắt ngày càng thưa → nghĩ tới amortized.
  • "Nhân đôi khi đầy" (mảng động, hash table mở rộng) là dấu hiệu kinh điển của amortized O(1).
  • Đừng nhầm: amortized O(1) không có nghĩa mọi lần đều O(1) — chỉ là trung bình O(1).

7. 🎮 Trò chơi: Hiểu amortized​

🎮 Hiểu amortizedCâu 1/3· Điểm 0· 🔥 0

Amortized = chi phí TRUNG BÌNH trên nhiều lần, khi cú đắt hiếm và thưa dần.

list.append trong Python có độ phức tạp amortized là?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Phân tích amortized đo cái gì?
2. Khi mảng động đầy, một lần thêm có thể tốn?

9. Hoàn thành​

…

☑️ Hết Chương 1.2 (Độ phức tạp)! Tiếp theo: 1.3.1 — Đệ quy: base case & recursive case.