Auxiliary space là gì?

Thuật ngữ độ phức tạp không gian (space complexity) được sử dụng sai cho không gian phụ (auxiliary space) ở nhiều nơi. Sau đây là các định nghĩa đúng về không gian phụ (auxiliary space) và độ phức tạp không gian.

Không gian phụ (auxiliary space) là không gian (space) bổ sung hoặc không gian tạm thời được sử dụng bởi một thuật toán (algorithm).

Độ phức tạp không gian của một thuật toán là tổng không gian mà thuật toán lấy ra đối với kích thước đầu vào (input size). Độ phức tạp không gian bao gồm cả không gian phụ (auxiliary space) và không gian được sử dụng bởi đầu vào.

Ví dụ nếu chúng ta muốn so sánh các thuật toán sắp xếp (sorting) trên cơ sở không gian, thì không gian phụ (auxiliary space) sẽ là một tiêu chí tốt hơn độ phức tạp không gian. Sắp xếp trộn (merge sort) sử dụng không gian phụ O(n) do sử dụng mảng mới để giải quyết bài toán, sắp xếp chèn (insertion sort) và sắp xếp vun đống (heap sort) sử dụng không gian phụ O(1) . Tuy nhiên, độ phức tạp không gian của tất cả các thuật toán sắp xếp này là O(n).

Độ phức tạp không gian là một khái niệm song song với độ phức tạp thời gian (time complexity). Nếu chúng ta cần tạo một mảng (array) có kích thước n, điều này sẽ yêu cầu không gian O(n). Nếu chúng ta tạo một mảng hai chiều có kích thước n * n, điều này sẽ yêu cầu không gian O(n²).