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

Độ phức tạp không gian mô tả lượng bộ nhớ mà thuật toán sử dụng theo kích thước đầu vào $N$. Cũng dùng ký hiệu Big-O như độ phức tạp thời gian.

Tại sao quan trọng?

Mỗi bài toán có giới hạn bộ nhớ (thường là 256 MB). Nếu vượt quá, bạn sẽ nhận kết quả MLE (Memory Limit Exceeded).

Kích thước kiểu dữ liệu trong C++

Ước lượng bộ nhớ

Công thức: Số phần tử × kích thước mỗi phần tử

Ví dụ:

• Mảng int 1 triệu phần tử: ${10}^6\times 4=4$ MB
• Mảng long long 1 triệu phần tử: ${10}^6\times 8=8$ MB
• Ma trận int $1000\times 1000$: ${10}^6\times 4=4$ MB
• Ma trận int ${10}^4\times {10}^4$: ${10}^8\times 4=400$ MB ❌ (quá giới hạn!)

Các mức độ phức tạp không gian

Ví dụ

$O(1)$ — không gian hằng số

long long sum = 0;
for (int i = 0; i < n; i++) sum += a[i];

$O(N)$ — tuyến tính

vector<long long> prefix(n+1, 0);
for (int i = 0; i < n; i++)
    prefix[i+1] = prefix[i] + a[i];

$O(N^2)$ — bình phương

int adj[1000][1000];  // 4 MB với N = 1000

Lưu ý thực tế

• Stack đệ quy sâu cũng tốn bộ nhớ. Đệ quy sâu $N={10}^5$ có thể bị RE do stack overflow.
• Trong Python, mọi đối tượng đều có overhead — một int Python tốn ~28 bytes (so với 4 bytes trong C++).

import sys
a = [0] * 10**6
print(sys.getsizeof(a))  # ~8 MB

int a[1000000];  // 4 MB chính xác