Time and Space Complexity

시간 복잡도:

• O(d * (n + k))
  • 여기서 n은 요소의 개수, k는 기수(10), d는 가장 큰 값의 자릿수입니다. d번의 각 패스(pass)는 O(n + k)의 작업을 수행합니다.
• d가 작고 고정되어 있을 때, 이는 O(n)처럼 동작하며, 비교 정렬의 O(n log n)보다 빠릅니다.

공간 복잡도:

• O(n + k)
  • 각 패스마다 크기가 n인 출력 배열과 크기가 k인 카운트 배열을 생성합니다.

요약:

• 기수 정렬(Radix Sort)은 자릿수가 제한된 정수 키에 대해 O(n log n)을 능가할 수 있는 안정적인 비비교 정렬입니다.
• 키를 자릿수로 나눌 수 있어야 하고 추가 메모리가 필요하며, 이 버전은 비음수 정수를 가정합니다.