Data Structures & Algorithms - Tập 3: Độ phức tạp không gian (Space Complexity)

Độ phức tạp không gian không phải là kích thước tệp code của bạn hay dung lượng file trên ổ cứng.

Nó là lượng bộ nhớ (RAM) thêm mà thuật toán cần để thực thi công việc. Hãy tưởng tượng bộ não của chúng ta khi tính toán:

• Một phép tính đơn giản có thể nhẩm trong đầu (O(1) Space).

• Một bài toán phức tạp hơn cần giấy nháp để ghi chép lại các bước trung gian (Auxiliary Space). Nếu con số input càng lớn mà lượng giấy nháp bạn cần càng nhiều, thì đó chính là O(n) Space.