기수 정렬은 숫자에 대한 비교 없이 정렬하는 알고리즘입니다. 이 알고리즘은 숫자를 자릿수별로 비교하여 정렬하는 비교 기반 정렬 알고리즘과는 다르게 동작합니다. 이에 따라, 기수 정렬 알고리즘은 최선/최악/평균 시간 복잡도를 가집니다.

최선/최악/평균 시간 복잡도

• 최선 시간 복잡도는 O(n) 입니다. 단, 숫자들이 균등하게 분포되어 있다는 가정 하에 최선 시간 복잡도를 가집니다.

• 최악 시간 복잡도 역시 O(n) 입니다. 숫자들이 동일한 자릿수를 가지는 경우, 모든 숫자를 동일한 자릿수에 위치시켜야 하므로 최악의 경우 시간 복잡도가 O(n)이 됩니다.

• 평균 시간 복잡도 또한 O(n)입니다. 숫자들의 분포에 의존하지 않고 일정한 성능을 보장하기 때문에 평균 시간 복잡도가 O(n)이 됩니다.

기수 정렬 알고리즘의 성능은 입력으로 주어지는 숫자 자릿수의 크기에 의해 영향을 받습니다. 일반적으로 입력 크기에 의존하지 않고 일정한 성능을 보이므로 대규모 데이터셋에 대해 유용합니다.

참고문헌:

• https://en.wikipedia.org/wiki/Radix_sort
• https://www.geeksforgeeks.org/radix-sort/