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

Độ phức tạp không gian

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

Tốc độ không phải thứ duy nhất quan trọng — bộ nhớ cũng vậy. Bài này dạy cách đo độ phức tạp không gian (thuật toán dùng thêm bao nhiêu bộ nhớ theo n), và vì sao đôi khi ta cố tình tốn thêm bộ nhớ để chạy nhanh hơn.

1. Trực quan: bàn làm việc rộng cỡ nào?​

Thời gian giống bạn làm nhanh cỡ nào; không gian giống bàn làm việc của bạn cần rộng cỡ nào. Một thuật toán có thể nhanh nhưng ngốn bộ nhớ khổng lồ — và nếu hết RAM, máy sẽ chậm rề hoặc sập. Vì vậy ta đo cả hai.

Độ phức tạp không gian = lượng bộ nhớ thêm thuật toán cần, theo kích thước đầu vào n. (Không tính phần đầu vào — ta tính phần phát sinh trong lúc chạy.)

2. Hai mức hay gặp​

O(1) không gian (in-place — tại chỗ): chỉ dùng vài biến phụ, không phụ thuộc n.

def tong(A):
    s = 0            # 1 bien duy nhat
    for x in A:
        s += x
    return s         # O(1) khong gian

O(n) không gian: tạo cấu trúc phụ lớn bằng dữ liệu (mảng mới, set, dict).

def binh_phuong(A):
    kq = []          # mang moi, lon dan bang A
    for x in A:
        kq.append(x * x)
    return kq         # O(n) khong gian

3. Chạy debug: "nhìn" bộ nhớ thêm lớn lên​

Bước qua hàm tạo mảng phụ với A = [2, 3, 4]. Để ý list kq phình ra bằng A:

🐞 Bộ nhớ thêm O(n), A = [2, 3, 4]Bước 1/4
1def binh_phuong(A):
2  kq = []
3  for x in A:
4      kq.append(x * x)
5  return kq
Biến tại bước này
kq[]
👉 Tạo list phụ rỗng — đây là bộ nhớ THÊM.

So với hàm tong ở trên (chỉ 1 biến s, không đổi dù A to cỡ nào) — đó là khác biệt O(1) và O(n) về không gian.

4. Đảo mảng: in-place (O(1)) vs tạo mới (O(n))​

Cùng việc "đảo ngược mảng", hai cách tốn bộ nhớ khác nhau. Bấm Run:

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

Cả hai cùng O(n) thời gian, nhưng cách 2 chỉ tốn O(1) không gian (vài biến), còn cách 1 tốn O(n) (mảng mới). Khi dữ liệu khổng lồ, in-place tiết kiệm bộ nhớ đáng kể.

5. Đánh đổi thời gian ↔ không gian​

Nhớ mẹo set ở bài 1.2.1? Ta tốn O(n) bộ nhớ (cái set) để hạ thời gian từ O(n²) xuống O(n). Đó là đánh đổi kinh điển:

Thường có thể đổi bộ nhớ lấy tốc độ (nhớ kết quả để khỏi tính lại) hoặc ngược lại. Không có bữa trưa miễn phí — chọn cái nào tùy bài toán và tài nguyên.

Quy hoạch động (học sau) chính là nghệ thuật đánh đổi này: tốn bộ nhớ lưu kết quả con để tránh tính đi tính lại.

6. Lưu ý: đệ quy cũng tốn không gian​

Mỗi lời gọi hàm chiếm một chỗ trên ngăn xếp lời gọi (call stack). Đệ quy sâu n tầng → tốn O(n) không gian dù không tạo mảng nào. Ta sẽ gặp lại ở bài 1.3.2.

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

  • Chỉ vài biến phụ, sửa tại chỗ → O(1) không gian.
  • Tạo mảng/set/dict lớn bằng n → O(n) không gian.
  • Đệ quy sâu theo n → O(n) không gian (vì call stack).

8. 🎮 Trò chơi: Đoán độ phức tạp KHÔNG GIAN​

🎮 Đoán không gianCâu 1/4· Điểm 0· 🔥 0

Chỉ tính bộ nhớ THÊM (ngoài đầu vào). Vài biến = O(1); cấu trúc lớn bằng n = O(n).

Tính tổng mảng bằng một biến cộng dồn.

9. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Độ phức tạp không gian đo cái gì?
2. "In-place" (tại chỗ) thường có độ phức tạp không gian là?
3. Mẹo dùng set để hạ thời gian từ O(n²) xuống O(n) là ví dụ của?

10. Hoàn thành​

…

☑️ Tiếp theo: 1.2.6 — Phân tích amortized (khi một thao tác thỉnh thoảng đắt nhưng trung bình vẫn rẻ).