Time and Space Complexity

시간 복잡도:

• O(n + k)
  • 여기서 n은 요소의 개수이고 k는 값의 범위(max + 1)입니다. 카운트하기 위해 한 번 순회하고, 재구성하기 위해 카운트 배열을 한 번 더 순회합니다.
• k가 작고 고정되어 있을 때, 이는 실질적으로 O(n)이며, 비교 정렬의 O(n log n)보다 빠릅니다.

공간 복잡도:

• O(n + k)
  • 카운트 배열은 O(k)를 사용하고 출력 배열은 O(n)을 사용합니다.

요약:

• 계수 정렬(Counting Sort)은 작은 정수 범위에 대해 선형 시간에 실행되는 안정적인 비비교 정렬입니다.
• 값의 범위 k가 매우 클 경우 카운트 배열이 거대해지기 때문에 적합하지 않습니다. 이 버전은 음수가 아닌 정수를 가정합니다.