Space complexity là gì?

Bạn có thể đã nghe nói về thuật ngữ này, độ phức tạp không gian (space complexity), nó luôn xoay quanh khi nói về độ phức tạp thời gian (time complexity). Độ phức tạp không gian ? Đó là không gian (space) hoặc bộ nhớ (memory) được yêu cầu bởi bất kỳ thuật toán nào (algorithm). Nó phụ thuộc trực tiếp hoặc tỷ lệ với kích thước đầu vào (input size) mà thuật toán thực hiện. Để tính toán độ phức tạp không gian, tất cả những gì bạn phải làm là tính toán lượng bộ nhớ (memory, space) mà các biến (variabe) sử dụng trong một thuật toán. Lượng bộ nhớ sử dụng càng ít, thuật toán thực thi càng nhanh. Cũng cần biết rằng độ phức tạp thời gian và không gian không liên quan đến nhau.