💾 Độ phức tạp bộ nhớ

Độ phức tạp thời gian trả lời câu hỏi “chạy chậm cỡ nào khi dữ liệu lớn dần”; độ phức tạp bộ nhớ (space complexity) trả lời câu hỏi tương tự nhưng cho bộ nhớ: lượng bộ nhớ phụ trội tăng nhanh cỡ nào theo kích thước đầu vào. Cách suy luận và ký hiệu (Big O) hoàn toàn giống với độ phức tạp thời gian, chỉ khác đối tượng đo.

Đo cái gì?

Khi phân tích bộ nhớ, người ta thường không tính vùng nhớ chứa dữ liệu đầu vào (input) - vì đó là thứ bài toán đưa cho bạn, không phải thứ thuật toán tạo ra. Thứ cần đếm là bộ nhớ phụ trội (extra/auxiliary space) mà thuật toán cấp phát thêm trong lúc chạy, chủ yếu đến từ ba nguồn:

• Biến và cấu trúc dữ liệu tạm - mảng mới, hash set, danh sách kết quả… được tạo ra trong quá trình tính toán.
• Ngăn xếp lời gọi hàm (call stack) - mỗi lần một hàm gọi hàm khác (đặc biệt là đệ quy gọi chính nó), hệ thống cấp một khung nhớ mới để lưu biến cục bộ và điểm quay về; khung này chỉ được giải phóng khi hàm đó return.
• Bộ nhớ cho kết quả trả về (output) - nếu thuật toán phải trả về một cấu trúc dữ liệu mới (chứ không sửa trực tiếp trên input).

Ví dụ 1: Đảo ngược mảng - in-place và tạo bản sao

In-place - O(1) bộ nhớ phụ trội: hoán đổi trực tiếp trên mảng gốc bằng hai con trỏ, không cấp phát gì thêm ngoài vài biến tạm.

def reverse_inplace(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    # Chỉ dùng thêm left, right -> O(1) space

Tạo bản sao - O(n) bộ nhớ phụ trội: trả về một mảng hoàn toàn mới, giữ nguyên mảng gốc.

def reverse_copy(arr):
    return arr[::-1]  # cấp phát mảng mới cùng kích thước -> O(n) space

Hai cách trên có cùng độ phức tạp thời gian (O(n) - đều phải chạm mỗi phần tử một lần), nhưng khác hẳn về bộ nhớ. Chọn cách nào tùy vào việc bạn có được phép sửa trực tiếp dữ liệu gốc hay không.

Ví dụ 2: Đệ quy tốn bộ nhớ ngăn xếp

Mỗi lời gọi đệ quy chưa return sẽ chiếm một khung nhớ trên call stack. Với hàm tính giai thừa gọi đệ quy sâu n tầng trước khi tầng cuối cùng trả về:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)   # n tầng gọi lồng nhau chưa return

Tại thời điểm sâu nhất, có n khung nhớ đang tồn tại đồng thời trên call stack → O(n) bộ nhớ, dù bản thân hàm không hề khai báo mảng hay cấu trúc dữ liệu nào. Đây là lý do đệ quy thường tốn bộ nhớ hơn vòng lặp tương đương:

def factorial_loop(n):
    res = 1
    for i in range(2, n + 1):
        res *= i
    return res   # chỉ 1 khung nhớ duy nhất -> O(1) space

Mẹo

Đây cũng là lý do đệ quy quá sâu gây lỗi “stack overflow”: call stack có giới hạn dung lượng, và mỗi tầng đệ quy chưa return sẽ ăn vào giới hạn đó.

Ví dụ 3: Đánh đổi bộ nhớ lấy tốc độ

Quay lại bài toán tìm phần tử trùng lặp ở trang trước: cách brute-force chạy O(n²) thời gian nhưng chỉ tốn O(1) bộ nhớ phụ trội (không cấp phát gì thêm), trong khi cách dùng hash set chạy O(n) thời gian nhưng tốn thêm O(n) bộ nhớ để lưu tập seen.

Đây là một đánh đổi (trade-off) rất thường gặp trong thiết kế thuật toán: giảm thời gian bằng cách trả giá bằng bộ nhớ, hoặc ngược lại. Không có lựa chọn nào “đúng tuyệt đối” - nó phụ thuộc vào bài toán: xử lý dữ liệu cực lớn trên thiết bị hạn chế RAM thì ưu tiên tiết kiệm bộ nhớ; cần phản hồi nhanh (ví dụ tra cứu real-time) thì thường chấp nhận tốn thêm bộ nhớ để đổi lấy tốc độ.

Các mức độ phức tạp bộ nhớ thường gặp

Giống hệt độ phức tạp thời gian, bộ nhớ cũng có các bậc quen thuộc:

Bậc	Ý nghĩa	Ví dụ
O(1)	Vài biến cố định, không phụ thuộc n	Hoán đổi in-place, vòng lặp tích lũy
O(log n)	Đệ quy chia đôi mỗi tầng	Binary search viết bằng đệ quy
O(n)	Một cấu trúc dữ liệu tỷ lệ với input	Tạo mảng/hash set mới, đệ quy tuyến tính
O(n²)	Cấu trúc hai chiều	Ma trận kề của đồ thị, bảng quy hoạch động 2D

Chú ý

O(log n) bộ nhớ chỉ đúng khi đệ quy chia đôi dữ liệu mỗi tầng (như binary search) - vì khi đó số tầng đệ quy tối đa là log n. Đừng nhầm với thời gian chạy: một thuật toán có thể chạy O(n) thời gian nhưng chỉ tốn O(log n) hoặc O(1) bộ nhớ, tùy cách cài đặt.

Tóm tắt

• Bộ nhớ phụ trội đến từ ba nguồn: biến/cấu trúc dữ liệu tạm, call stack của đệ quy, và bộ nhớ cho output.
• Cùng độ phức tạp thời gian, hai cách cài đặt vẫn có thể khác nhau về bộ nhớ (in-place so với tạo bản sao).
• Đệ quy thường tốn bộ nhớ hơn vòng lặp tương đương, vì mỗi tầng gọi chưa return chiếm một khung nhớ trên call stack.
• Giảm thời gian bằng cách tốn thêm bộ nhớ (hoặc ngược lại) là đánh đổi rất phổ biến - không có lựa chọn đúng tuyệt đối, chỉ có lựa chọn phù hợp với bài toán.