Auxilary Space와 Space Complexity

Auxiliary space

Auxiliary space : 알고리즘에 의해 요구되는 임시 space를 의미한다. (Array 또는 Pointer 등)

Space Complexity : Input size에 따라 알고리즘이 차지하는 공간에 대한 참조를 의미한다. 이것은 input에 의해 사용되는 공간과 auxiliary space를 포함하는 개념이다.

예를 들어, Sorting Algorithm 와 같이 무언가를 비교하는 것의 경우, Auxiliary Space를 참조하는 것이 더 낫다 => 이유: Space complexity의 경우, sorting algorithm 같은 경우는 주어진 input size에 따른 space complexity는 항상 O(N)이기 때문이다.
(insertion sort와 heap sort는 O(1)의 auxiliary space를 사용하는 반면에 merge sort는 주어진 조건에 따라 임시 subarray등을 생성하므로 O(n)의 auxiliary space를 사용한다.)

결론

Space Complexity는 Auxiliary space를 포괄하는 개념이고, 일반적으로 알고리즘에서는 Space Complexity를 확인하지만 Sorting Algorithm과 같은 특정 알고리즘 Topic에서는 Space Compelxity가 같고, 알고리즘별로 중간에 사용되는 임시 공간(Auxiliary space)이 다르기 때문에 Auxiliary space를 다룬다.