Cả sê-ri này đo thời gian — nhanh hay chậm. Nhưng một thuật toán còn tiêu một tài nguyên thứ hai: bộ nhớ. Độ phức tạp không gian đếm lượng bộ nhớ phụ nó cần theo n, và nó thường bị xem nhẹ — "RAM rẻ mà, cứ cấp phát thoải mái". Bài này đo RAM thật (đọc VmHWM, đỉnh bộ nhớ, từ /proc) của vài thuật toán, và cho thấy không gian không hề là tài nguyên vô hạn phụ: nó là một bức tường cứng, và nó đổi qua đổi lại với thời gian theo những cách phải đo mới thấy.
Không gian: cùng ký hiệu O, khác hậu quả
Độ phức tạp không gian (space complexity) đo lượng bộ nhớ phụ — ngoài phần lưu chính đầu vào — một thuật toán cần khi n lớn dần. Nó dùng cùng ký hiệu O như thời gian: O(1) nghĩa là bộ nhớ phụ không đổi dù n bao lớn (một vài biến); O(n) nghĩa là bộ nhớ phụ tỉ lệ với n (một mảng cỡ n); O(n²) nghĩa là bình phương (một ma trận n×n). Ngăn xếp đệ quy cũng là không gian: đệ quy sâu n dùng O(n) ngăn xếp.
Nhưng có một khác biệt lớn giữa hết thời gian và hết không gian. Chậm là khó chịu; hết bộ nhớ là chết. Khi chương trình đòi hơn RAM có, hệ điều hành không cho nó chạy chậm lại — nó giết tiến trình (OOM, out-of-memory). Không gian là một bức tường cứng, và với thuật toán O(n²) không gian, bức tường ấy ở gần hơn nhiều so với khi hết thời gian.
Đo: ma trận O(V²) đụng tường, danh sách O(V+E) thì không
Ví dụ kinh điển: lưu một đồ thị V đỉnh. Cách ma trận kề dùng một bảng V×V (O(V²) bộ nhớ); cách danh sách kề chỉ lưu các cạnh thật có (O(V+E)). Tôi cấp phát và chạm hết bộ nhớ mỗi cách (chạm để nó thực sự vào RAM), rồi đọc đỉnh bộ nhớ:
Bộ nhớ (VmHWM) theo số đỉnh V:
V | ma trận kề O(V²) | danh sách kề O(V+E), bậc 10
5.000 | 24,9 MB | 1,2 MB
10.000 | 96,4 MB | 1,4 MB
20.000 | 382,5 MB | 1,8 MB
40.000 | 1.526,9 MB | 2,6 MB
Cột ma trận xác nhận O(V²): mỗi lần V gấp đôi, RAM gấp bốn (24,9 → 96,4 → 382,5 → 1527). Ở V = 40.000, ma trận đã ngốn 1,5 GB, còn danh sách chỉ 2,6 MB — chênh gần 600 lần. Và đây là chỗ bức tường lộ ra: trên máy 8 GB này, ma trận sẽ chạm trần RAM ở khoảng V = 90.000 và bị OOM giết, trong khi danh sách vẫn ở mức vài megabyte và chạy thoải mái tới hàng triệu đỉnh. Không phải "chậm hơn ở V lớn" — mà là "không chạy được nữa". Với đồ thị thưa (E ≪ V², như hầu hết đồ thị thực), chọn ma trận là tự dựng một bức tường ngay trước mặt.
Một lần tôi đo hớ: nhiều khi bạn giữ không gian không cần
Định kiến tôi mang vào: "chỉ tối ưu thời gian, bộ nhớ cứ để đó". Đo hai điều làm tôi phải nghĩ lại. Thứ nhất là bức tường OOM ở trên. Thứ hai tinh tế hơn: rất nhiều khi ta cấp phát O(n) mà chẳng cần. Lấy quy hoạch động: công thức Fibonacci dp[i] = dp[i-1] + dp[i-2]. Cách sách giáo khoa dựng cả bảng dp[0..n] (O(n) không gian). Nhưng để tính giá trị thứ n, ta chỉ cần hai giá trị gần nhất — dùng một biến "cuộn" (rolling) O(1). Tôi đo cả hai ở n = 50 triệu:
DP Fibonacci (mod), n = 50 triệu:
bảng đầy đủ O(n) : 382,5 MB | 133 ms
cuộn 2 biến O(1) : 1,0 MB | 126 ms
Cùng thời gian (~130 ms), nhưng bản cuộn dùng 1 MB thay vì 382 MB — tiết kiệm 382 lần bộ nhớ miễn phí (thậm chí nhanh hơn chút vì không cấp phát mảng lớn). Cái bảng O(n) mà cách ngây thơ giữ suốt là không gian thừa: nó lưu 50 triệu giá trị trung gian mà không bao giờ được đọc lại. Bài học: trước khi cấp một mảng O(n), hỏi "mình có thật sự cần giữ hết không, hay chỉ cần vài phần tử gần nhất". Rất nhiều DP một chiều rút được từ O(n) xuống O(1) không gian y như vậy.
Đo hớ thứ hai: không gian đổi được với thời gian, cả hai chiều
Nếu O(1) không gian luôn tốt, thì cứ chọn thuật toán tại chỗ? Không đơn giản vậy. Tôi so hai cách sắp xếp 30 triệu số nguyên: heapsort (sắp tại chỗ, O(1) bộ nhớ phụ) và merge sort (cần một bộ đệm O(n)):
Sắp 30 triệu int (đầu vào ~114 MB):
heapsort (tại chỗ) : 7.666 ms | VmHWM 115,5 MB
merge sort (+đệm n) : 2.061 ms | VmHWM 229,4 MB
Đúng như dự đoán về không gian: merge sort tốn gấp đôi RAM (229 so 115 MB) vì cần bộ đệm bằng cả mảng. Nhưng về thời gian thì bất ngờ: merge sort nhanh hơn 3,7 lần dù cùng O(n log n)! Lý do là cache: heapsort tuy tại chỗ nhưng truy cập nhảy khắp đống (mỗi lần "sàng" nhảy tới con/cha ở xa) — cực kỳ kém thân thiện cache; merge sort quét tuần tự, thân thiện cache. Vậy đây là một đánh đổi thời gian–không gian thật, chạy cả hai chiều: heapsort mua RAM ít bằng thời gian nhiều; merge sort mua tốc độ bằng RAM gấp đôi. Không cái nào "đúng" tuyệt đối — nếu bạn kẹt RAM, chọn heapsort; nếu bạn cần tốc độ và có RAM, chọn merge. Con dao trượt giữa hai đầu, và bạn chọn điểm theo ràng buộc.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: đo cả bộ nhớ, không chỉ thời gian — nhất là độ dốc theo n. Một thuật toán O(n²) không gian có thể chạy ngon trên dữ liệu test nhỏ rồi chết trên dữ liệu thật lớn, và triệu chứng không phải "chậm dần" mà là "bị kill đột ngột" — khó chẩn đoán hơn nhiều. Khi chọn cấu trúc, hỏi độ phức tạp không gian của nó ngang với hỏi thời gian: ma trận kề hay danh sách kề, bảng DP đầy đủ hay cuộn, đọc cả file vào RAM hay xử lý theo luồng.
Hệ quả thứ hai: không gian là một biến để tối ưu, và thường tối ưu được rất nhiều mà không mất gì. Bản cuộn O(1) của DP cho thấy 382 lần bộ nhớ tiết kiệm miễn phí. Xử lý theo luồng (streaming) thay vì nạp cả tập, dùng chỉ số nhỏ gọn thay vì bản sao đầy đủ, bitset thay mảng bool — nhiều kỹ thuật cắt không gian mà giữ nguyên (hoặc cải thiện) thời gian nhờ cache. Đừng để "RAM rẻ" thành cái cớ cấp phát bừa; ở quy mô lớn, bộ nhớ là thứ chạm trần trước.
Hệ quả thứ ba là bài học đo lường bao trùm: thời gian và không gian là hai trục, và tối ưu chỉ một trục là thấy nửa bức tranh. Con số mang theo: ma trận kề O(V²) ngốn 1.527 MB ở V=40.000 (V×2 → RAM×4) và OOM ở V~90.000 trong khi danh sách kề chỉ 2,6 MB; DP cuộn O(1) dùng 1 MB thay vì 382 MB của bảng đầy đủ ở cùng thời gian; và merge sort tốn gấp đôi RAM nhưng nhanh hơn heapsort 3,7 lần nhờ cache. Không gian là một bức tường cứng (hết RAM là chết, không phải chậm), một biến tối ưu được (thường miễn phí), và một đầu của cán cân đổi với thời gian. Đo cả hai trục, và chọn điểm hợp với ràng buộc thật của bài toán.
Thử ba mươi giây
Chạy một chương trình bất kỳ của bạn dưới /usr/bin/time -v ./chương-trình (Linux) và nhìn dòng Maximum resident set size — đó là đỉnh bộ nhớ thật, cùng thứ VmHWM bài này đo. Chạy nó với đầu vào nhỏ rồi đầu vào gấp đôi, so hai con số: nếu bộ nhớ gấp đôi thì bạn đang ở O(n) không gian, nếu gấp bốn thì O(n²) — và bạn vừa đo được độ dốc không gian của chính mình. Rồi thử một thí nghiệm nhỏ trong đầu với bất kỳ vòng lặp nào tích lũy vào một danh sách: bạn có thật cần giữ cả danh sách, hay chỉ cần tổng/max/phần tử cuối? Mỗi lần câu trả lời là "chỉ cần vài cái", bạn vừa tìm thấy một chỗ cắt O(n) xuống O(1) — thứ mà, như bài này đo, thường không tốn một mili giây nào.
