Cấu trúc dữ liệu và Giải thuật Bài 4: Độ phức tạp không gian (Space Complexity) & Bài toán đánh đổi (Trade-off).

Trong thế giới lý tưởng, chúng ta muốn thuật toán của mình chạy nhanh như chớp và không tốn một chút dung lượng bộ nhớ nào. Nhưng thực tế phũ phàng của khoa học máy tính là tài nguyên phần cứng luôn có giới hạn. Nếu Bài 3 giúp bạn đo lường xem thuật toán "đốt" bao nhiêu thời gian (CPU), thì Bài 4 sẽ giúp bạn biết thuật toán đó "ngốn" bao nhiêu dung lượng RAM thông qua Độ phức tạp không gian (Space Complexity).

1. Độ phức tạp không gian (Space Complexity) là gì?

Độ phức tạp không gian là tổng lượng bộ nhớ (RAM) mà một thuật toán cần để chạy từ lúc bắt đầu đến khi kết thúc, tính theo sự tăng trưởng của kích thước đầu vào ($n$).

Tổng không gian này được cấu thành từ hai phần:

1. Input Space (Không gian đầu vào): Dung lượng bộ nhớ để lưu trữ chính bản thân dữ liệu đầu vào. Ví dụ: hệ thống truyền vào một mảng 1 triệu phần tử, bản thân mảng đó đã chiếm RAM.

2. Auxiliary Space (Không gian phụ trợ): Dung lượng bộ nhớ tăng thêm mà thuật toán cần tạo ra (các biến tạm, mảng mới, bảng băm, hoặc bộ nhớ cho Call Stack khi dùng đệ quy) để giải quyết bài toán.

Trong các buổi phỏng vấn hoặc khi đánh giá tối ưu thuật toán, thuật ngữ "Space Complexity" thường ngầm ám chỉ Auxiliary Space – tức là bạn cần "vay mượn" thêm bao nhiêu bộ nhớ ngoài phần dữ liệu đã được cung cấp.

2. Các cấp độ Big-O trong Bộ nhớ

Cách tính Big-O cho không gian hoàn toàn tương đồng với thời gian:

• $O(1)$ - Không gian hằng số (In-place): Thuật toán chỉ sử dụng thêm một vài biến số tạm thời (số nguyên, con trỏ). Dù bạn sắp xếp 10 phần tử hay 1 tỷ phần tử, lượng RAM dùng thêm vẫn không đổi. (Ví dụ: Thuật toán sắp xếp nổi bọt Bubble Sort, Kỹ thuật hai con trỏ Two Pointers).

• $O(n)$ - Không gian tuyến tính: Thuật toán tạo ra một cấu trúc dữ liệu mới có kích thước tỷ lệ thuận với đầu vào. (Ví dụ: Copy mảng cũ sang mảng mới, dùng Hash Map để lưu trữ mảng, hoặc hàm đệ quy gọi $n$ lần lồng nhau tạo ra $n$ khung bộ nhớ trong Call Stack).

• $O(n^2)$ - Không gian bậc hai: Thường xuất hiện khi bạn tạo ra một ma trận 2 chiều (Grid) từ một tập dữ liệu 1 chiều. Nếu $n = 1000$, bạn tốn thêm 1 triệu ô nhớ. (Ví dụ: Bảng quy hoạch động 2D để tìm chuỗi con chung).

3. Bài toán đánh đổi: Không gian vs. Thời gian (Space-Time Trade-off)

Đây là một trong những nguyên lý vĩ đại nhất của kỹ thuật phần mềm: Để chạy nhanh hơn, bạn thường phải dùng nhiều RAM hơn. Để tiết kiệm RAM, bạn thường phải chấp nhận CPU chạy chậm lại.

Hãy xem xét bài toán: Kiểm tra xem một mảng có phần tử trùng lặp hay không.

Lựa chọn 1: Tiết kiệm RAM, hy sinh Tốc độ ($O(1)$ Space, $O(n^2)$ Time)

Bạn sử dụng hai vòng lặp lồng nhau, so sánh từng phần tử với tất cả các phần tử còn lại. Cách này không tốn thêm một byte RAM nào ngoài vài biến chạy i, j ($O(1)$ Space), nhưng CPU phải cày ải một khối lượng phép tính khổng lồ ($O(n^2)$ Time).

Lựa chọn 2: Hy sinh RAM, tối ưu Tốc độ ($O(n)$ Space, $O(n)$ Time)

Bạn tạo một Bảng băm (Set/Hash Map) để lưu các số đã duyệt qua. Duyệt mảng một lần, thấy số mới thì nhét vào Set, nếu số đã tồn tại trong Set tức là có trùng lặp. Tốc độ thực thi tăng lên thần kỳ chỉ còn $O(n)$, nhưng bạn phải cấp phát thêm một vùng nhớ có kích thước $O(n)$ để chứa cấu trúc Set đó.

4. Ứng dụng Trade-off trong thiết kế hệ thống thực tế

Việc chọn "điểm rơi" trong bài toán đánh đổi phụ thuộc hoàn toàn vào môi trường phần cứng bạn đang lập trình:

• Hệ thống Backend / Cloud (Ưu tiên Thời gian): Máy chủ đám mây có thể mở rộng hàng trăm GB RAM rất dễ dàng, nhưng độ trễ (latency) chậm đi vài giây sẽ làm mất khách hàng. Do đó, các kỹ sư backend thường "đổ" RAM ra để mua lấy tốc độ. Điển hình là việc sử dụng hệ thống in-memory như Redis hay Memcached — ngốn toàn bộ RAM để cache dữ liệu, đổi lại tốc độ phản hồi API tính bằng mili-giây.

• Hệ thống nhúng / IoT (Ưu tiên Không gian): Khi lập trình vi điều khiển, bạn chỉ có vài chục đến vài trăm Kilobyte RAM trống. Tại đây, việc cấp phát một mảng động khổng lồ hay dùng Hash Map là hành động đánh sập hệ thống (Out of Memory). Kỹ sư bắt buộc phải sử dụng các thuật toán In-place ($O(1)$ Space) và chấp nhận CPU tính toán lâu hơn một chút.

• Phát triển Game / Đồ họa: Cần một "Lookup Table" (mảng lưu sẵn kết quả của các góc Sin/Cos) để nhân vật di chuyển mượt mà (tốn RAM), thay vì bắt CPU tính lại hàm lượng giác phức tạp trong mỗi khung hình (tốn CPU, làm tụt FPS).

Hiểu về Time và Space Complexity giúp bạn thoát khỏi việc phỏng đoán. Bạn biết chính xác mình đang đánh đổi tài nguyên nào để phục vụ cho giới hạn vật lý của dự án.

Ở bài học tiếp theo, chúng ta sẽ lật mở mảnh ghép cuối cùng của lý thuyết độ phức tạp để đánh giá toàn diện một thuật toán trước mọi tình huống dữ liệu.