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

huunguyen · Last updated 28, Tháng 3, 2026, 22:43

Độ 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.

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).

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!)

Ký hiệu	Ví dụ
$O (1)$	Chỉ dùng vài biến, không phụ thuộc $N$
$O (\log N)$	Stack đệ quy của tìm kiếm nhị phân
$O (N)$	Một mảng $N$ phần tử
$O (N^{2})$	Ma trận $N \times N$

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

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

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

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

Bình luận

Không có bình luận tại thời điểm này.