Hiểu sự phức tạp về không gian là thiết yếu khi thiết kế các thuật toán cho môi trường với bộ nhớ hạn chế. Nó giúp xác định bao nhiêu phần bổ sung một thuật toán đòi hỏi tương đối với kích thước nhập của nó. Bài này giải thích các khái niệm và phương pháp quan trọng để tính toán sự phức tạp không gian trong thiết lập như thế.

Cơ bản của sự phức tạp không gian

Độ phức tạp không gian đo số lượng bộ nhớ một thuật toán sử dụng trong khi thực hiện. Nó bao gồm cả bộ nhớ cố định (các biến) và bộ nhớ biến (các cấu trúc dữ liệu, chồng được đệ quy). Trong môi trường được kiểm tra trí nhớ, tối ưu hóa không gian là tối ưu để đảm bảo hiệu suất chương trình và ngăn chặn thất bại.

Các yếu tố ảnh hưởng đến việc sử dụng không gian

Một số yếu tố ảnh hưởng đến sự phức tạp không gian, bao gồm kích cỡ nhập, cấu trúc dữ liệu được dùng và gọi đệ quy. Chẳng hạn, thuật toán đệ quy có thể tiêu thụ thêm khoảng không gian xếp theo tỉ lệ đệ quy. Chọn cấu trúc dữ liệu thích hợp cũng có thể giảm khả năng tiêu dùng bộ nhớ.

Tính độ phức tạp không gian

Để tính độ phức tạp của không gian, hãy phân tích các thuật toán để nhận diện bộ nhớ được dùng ở mỗi bước. Xem kích thước của các biến, cấu trúc dữ liệu và gọi chồng. Viết tổng bộ nhớ thành một hàm số cho kích thước nhập, thường được ngụ ý là n. Tập trung vào các thuật ngữ trội nhất khi n tăng nhanh nhất.

  • Xác định các yêu cầu bộ nhớ cố định.
  • Đánh giá bộ nhớ bổ sung cho cấu trúc dữ liệu.
  • Tài khoản cho việc đệ quy lại cuộc gọi chồng nếu ứng dụng.
  • Chuyển toàn bộ bộ bộ nhớ thành hàm kích cỡ nhập.