Có một câu quen thuộc: "thêm phần tử vào vector là O(1)". Nhưng thêm phần tử đôi khi phải cấp vùng nhớ mới và sao chép toàn bộ mảng cũ sang — rõ ràng đó là O(n), không phải O(1). Hai điều này mâu thuẫn nhau, và như bài đầu sê-ri đã nói, hai con số mâu thuẫn thường nghĩa là ta đang đo nhầm đại lượng. Ở đây không phải đo nhầm — mà là hai đại lượng khác nhau đội cùng một cái tên O(1). Phân biệt chúng là toàn bộ nội dung của phân tích khấu hao, và bài này đo cả hai bằng đồng hồ.
Khấu hao: trung bình trên cả dãy, không phải lần tệ nhất
Phân tích khấu hao (amortized analysis) hỏi một câu khác với phân tích trường hợp tệ nhất. Trường hợp tệ nhất hỏi: một thao tác đơn lẻ, xấu nhất, tốn bao nhiêu? Khấu hao hỏi: chạy một dãy dài n thao tác, tổng chi phí chia cho n là bao nhiêu? Hai câu cho hai con số, và với nhiều cấu trúc dữ liệu, con số thứ hai nhỏ hơn hẳn — vì cái thao tác đắt kia rất hiếm khi xảy ra.
Mảng động (dynamic array, std::vector của C++, ArrayList của Java, list của Python, slice của Go) là ví dụ kinh điển nhất. Nó giữ một vùng nhớ liền có dung lượng (capacity) lớn hơn số phần tử đang có (length). Thêm một phần tử (push_back) khi còn chỗ trống chỉ là ghi vào một ô: O(1) thật. Nhưng khi length chạm capacity — mảng đầy — nó phải cấp một vùng nhớ mới lớn hơn, sao chép mọi phần tử cũ sang, rồi giải phóng vùng cũ. Riêng lần đó tốn O(n).
Câu hỏi đo được: nếu cứ mỗi vài lần thêm lại có một lần O(n), thì trung bình một lần thêm tốn bao nhiêu — và điều gì làm nó rẻ?
Đo: tổng tuyến tính, mỗi thao tác dưới một nano giây
Tôi viết một mảng động trong C tự nhân đôi dung lượng mỗi lần đầy (malloc vùng mới, memcpy toàn bộ, free vùng cũ — buộc một lần sao chép thật, không nhờ realloc mở rộng tại chỗ). Rồi đo tổng thời gian chèn n phần tử, với n tăng dần:
TĂNG ĐÔI (x2), tổng thời gian và ns mỗi thao tác:
n = 1.000.000 : 1,0 ms (~0,97 ns/thao tác)
n = 2.000.000 : 1,7 ms (~0,86 ns/thao tác)
n = 4.000.000 : 2,9 ms (~0,72 ns/thao tác)
n = 8.000.000 : 4,7 ms (~0,59 ns/thao tác)
n = 16.000.000: 8,4 ms (~0,53 ns/thao tác)
Nhân đôi n thì tổng thời gian cũng xấp xỉ nhân đôi (1,0 → 1,7 → 2,9 → 4,7 → 8,4): tổng là tuyến tính theo n. Và chi phí trung bình mỗi thao tác giữ ở mức dưới một nano giây, bị chặn trên, không tăng theo n (nó còn hơi giảm vì chi phí khởi động cố định được chia cho nhiều thao tác hơn). Đó chính là O(1) khấu hao: dù xen giữa có những lần sao chép O(n), trung bình mỗi lần thêm vẫn là hằng số. Câu "push_back là O(1)" đúng — nhưng nó nói về trung bình, không phải về từng lần.
Một lần tôi đo hớ: một thao tác lẻ không hề là hằng số
Con số 0,5 ns/thao tác dễ khiến ta kết luận gọn: "vậy mỗi push_back đều O(1), n lần là O(n) trơn tru". Tôi suýt viết đúng câu đó — và nó sai ở một chỗ quan trọng. Để thấy chỗ sai, đừng đo trung bình; hãy đo đường cong chi phí từng thao tác. Tôi đo riêng chi phí sao chép của mỗi lần realloc khi chèn tới 2,1 triệu phần tử:
realloc tại cap=1.024 : sao chép 1.024 phần tử -> 83 ns
realloc tại cap=16.384 : sao chép 16.384 phần tử -> 7.208 ns
realloc tại cap=262.144 : sao chép 262.144 phần tử-> 118.167 ns
realloc tại cap=1.048.576 : sao chép ~1 triệu phần tử-> 200.000 ns
realloc tại cap=2.097.152 : sao chép 2,1 triệu phần tử->392.291 ns
Đường cong này không hề phẳng. Phần lớn thao tác tốn vài nano giây, nhưng tại mỗi mốc lũy thừa của 2 có một gai: chi phí sao chép gấp đôi mỗi lần. Lần realloc cuối cùng — sao chép 2,1 triệu phần tử — tốn 392 micro giây, tức gấp khoảng 400.000 lần một push thường (~1 ns). Một thao tác đơn lẻ ở đúng thời điểm mảng đầy hoàn toàn không phải là hằng số; nó là O(n) với n là kích thước hiện tại.
Vậy vì sao trung bình vẫn là hằng số? Vì tuy mỗi gai cao gấp đôi, chúng lại thưa gấp đôi. Các lần sao chép là n, n/2, n/4, n/8, ... Cộng chuỗi hình học này lại: n + n/2 + n/4 + ... = 2n. Tổng mọi lần sao chép trong suốt quá trình chỉ là O(n), chia cho n thao tác ra O(1). Đây là chứng minh cổ điển của khấu hao, và đo đạc cho thấy nó đúng: tổng thời gian tuyến tính (bảng trên), dù đường cong per-op đầy gai.
Chỗ đo hớ nếu bỏ qua điều này: "O(1) khấu hao" không có nghĩa "mỗi thao tác đều nhanh". Nó có nghĩa "trung bình nhanh". Với phần lớn code, khác biệt không quan trọng. Nhưng với code nhạy độ trễ — hệ thống thời gian thực, vòng game 60 khung hình/giây, một dịch vụ đo p99 — cái gai 392µs kia là một cú giật độ trễ có thật, xảy ra đúng vào lần thêm phần tử thứ 2 triệu. Ở đó người ta thường reserve sẵn dung lượng để không bao giờ chạm mốc realloc, chính vì biết một thao tác lẻ không phải hằng số.
Đo hớ thứ hai: grow-by-1 "tiết kiệm bộ nhớ" là thảm họa O(n²)
Điều gì làm chuỗi sao chép cộng lại chỉ bằng 2n? Là hệ số tăng nhân đôi. Một suy nghĩ nghe hợp lý: nhân đôi thì lãng phí bộ nhớ (có lúc mảng chiếm gấp đôi số phần tử thật) — sao không tăng dung lượng thêm một phần tử mỗi lần cho tiết kiệm? Tôi đo thử, với cùng n = 200.000:
n = 200.000, các cách tăng dung lượng:
x2 (nhân đôi) : 0,07 ms
x1.5 : 0,08 ms
+1024 (tăng cộng) : 1,26 ms
+1 (grow-by-1) : 1.274,87 ms <- chậm 17.851 lần x2
Grow-by-1 chậm hơn nhân đôi gần mười tám nghìn lần. Lý do: nếu mỗi lần chỉ tăng thêm 1 ô, thì mỗi lần thêm đều làm mảng đầy, và mỗi lần đều sao chép lại từ đầu. Tổng chi phí là 1 + 2 + 3 + ... + n = n(n+1)/2 = O(n²). Tôi kiểm chứng bằng cách đo ở hai kích thước: n=100k tốn 324ms, n=200k tốn 1283ms — nhân đôi n thì thời gian gấp bốn, đúng dấu hiệu của O(n²). "Tiết kiệm bộ nhớ" hóa ra đổi một hằng số bộ nhớ nhỏ lấy một thảm họa thời gian.
Ngược lại, x1.5 gần như ngang x2 (0,08 so với 0,07 ms) mà lãng phí bộ nhớ ít hơn — đó là lý do nhiều thư viện thật (nhiều bản std::vector) chọn hệ số quanh 1,5 thay vì 2: vẫn là tăng nhân, nên vẫn cho tổng O(n) và khấu hao O(1), chỉ khác hằng số. Điểm mấu chốt: bất kỳ hệ số nhân nào > 1 đều cho khấu hao O(1); tăng cộng (một hằng số cố định) thì không — nó luôn dẫn tới O(n²), dù hằng số là +1 hay +1024 (chỉ chậm ít hơn, không đổi bậc).
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: hiểu "khấu hao" đúng nghĩa để không bị bất ngờ vì độ trễ. Khi tài liệu ghi "amortized O(1)", hãy đọc là "rẻ về trung bình, nhưng thỉnh thoảng có một thao tác đắt O(n)". Trong code thông thường, cứ dùng thoải mái. Trong vòng nóng nhạy độ trễ, nếu bạn biết trước số phần tử, gọi reserve(n) / ensureCapacity(n) một lần để cấp đủ dung lượng ngay từ đầu — bạn xóa sạch mọi lần realloc và mọi cái gai, đổi khấu hao O(1) lấy O(1) thật sự cho từng thao tác.
Hệ quả thứ hai: hệ số tăng là một quyết định thiết kế có hậu quả bậc độ phức tạp, không phải chi tiết vặt. Nếu bạn tự viết một cấu trúc kiểu mảng động (buffer, hàng đợi, string builder), tăng dung lượng theo nhân (×1,5 hay ×2), tuyệt đối đừng tăng theo cộng. Đây là một lỗi âm thầm: code chạy đúng, test nhỏ xanh, rồi ở dữ liệu lớn nó chậm gấp hàng nghìn lần mà không có lỗi nào — đúng kiểu "nhanh hay chậm chỉ lộ ra khi đo đường cong, không phải một điểm".
Hệ quả thứ ba: khấu hao đánh đổi bộ nhớ lấy thời gian, và đó là đánh đổi đáng. Nhân đôi dung lượng nghĩa là có lúc bạn giữ vùng nhớ gấp đôi số phần tử cần — lãng phí tới 50%. Nhưng nó biến chi phí chèn từ O(n²) thành O(n) tổng cộng. Cùng nhóm với chuyện cấp phát bộ nhớ: cấp nhiều một lần rồi dùng dần bao giờ cũng rẻ hơn cấp lắt nhắt từng chút. Con số mang theo: thêm phần tử vào mảng động là O(1) khấu hao nhờ tăng dung lượng theo hệ số nhân — tổng mọi lần sao chép là 2n = O(n); nhưng một thao tác lẻ tại mốc realloc vẫn là O(n) (đo được cái gai 392µs, gấp 400.000 lần push thường), và đổi sang tăng cộng grow-by-1 là rơi thẳng xuống O(n², chậm 17.851 lần). "O(1)" ở đây là một con số trung bình có điều kiện — biết điều kiện của nó thì mới dùng đúng.
Thử ba mươi giây
Trong Python, chạy thử: import sys; L=[]; [ (L.append(i), print(len(L), sys.getsizeof(L))) for i in range(20) ] — nhìn cột thứ hai (số byte cấp phát). Nó không tăng đều mỗi phần tử; nó nhảy bậc, giữ nguyên vài bước rồi đột ngột lớn hơn — đó chính là những lần realloc, và khoảng cách giữa các lần nhảy ngày một xa (tăng theo hệ số nhân). Rồi thử một thí nghiệm nhỏ trong bất kỳ ngôn ngữ nào: dựng một mảng lớn hai cách — một cách reserve dung lượng trước, một cách để nó tự lớn dần — và đo thời gian. Nếu cách reserve nhanh hơn rõ rệt, bạn vừa đo được chi phí của những lần sao chép mà khấu hao đã giấu vào con số trung bình.
