기수정렬에서 가장 중요한 것은, 이미 정렬된 순서를 흐트러트리지 않아야 하는, 안정성(stability)이다. 다시 말해서, 다음 자리를 정렬한다고 할 때, 이미 정렬된 순서대로 꺼내와서 배치해야 한다.
배열을 늘려가는 전략에는 여러가지가 있을 수 있다. 즉, 메모리 할당 전략이 어떤 것이 더 좋은가라는 것으로 바꿔 말할 수 있다. 문자 배열의 메모리를 할당 받는 전략에서는, 지수 형식으로 블럭을 할당하는게 더 효율적일 수 있지만, 이것은 메모리의 적절한 사용량을 생각한 것은 아니다. 다만, 단지 효율적인 시간에 대해서만 생각한 것이다.그렇다면, 한번에 대량의 메모리를 할당받는 것이 RAM이란 기계에서 최선의 할당전략이라고 할 수 있는데, 옳은 이야기인가?
앞서 이야기했던 배열 상황에서는, 줄어들지 않고 추가만 있는 상황을 가정한다. 즉, 경계에서 push, pop 연산이 연속적으로 일어나는 것이 최악의 상황이 아니라, 연속적으로 push 연산만 일어나는 것이 최악의 상황이 된다. 그렇다면, 이 경우, 필요한 연산량은 얼마인가? n - 1 번째 entry에 대해서 push 연산수는 상수 시간내에 처리된다고 할 수 있다. 하지만, n번째 엔트리가 추가되는 상황이라면, 모든 배열을 사용했기 때문에, 새로운 배열 추가가 필요하다. 2n 크기의 새로운 배열을 할당 받은 뒤에, n - 1만큼의 엔트리를 새로운 배열에 복사하는 연산, 그리고 마지막 엔트리를 추가하는 상수시간의 연산 1이 필요하다. 따라서, 2n + n - 1 + 1 = 3n의 연산량이 필요하며, n번째의 엔트리를 추가하는 상황에서의 평균값은 3n / n = 3, 즉 3의 연산량이 평균적으로 필요하다는 것을 알 수 있다.
Amortised Time Anaysis라는 것은 Big-Ο와 어떻게 다른가? 이들은 서로 비슷하지만 같지는 않다. Big-Ο는 하한을 의미하는, 최악의 경우를 생각한 표기이다. Amortised Time Analysis는 최악의 시간에 수행되는 평균수행시간을 의미한다. 위에서 계산한 것이 최악의 경우에 필요한 평균적인 연산량이라 할 수 있다.
Library/Algorithm