계수 정렬 . 4

계수 정렬은 가장 작은 데이터부터 가장 큰 데이터까지의 모든 범위를 포함할 수 있는 크기의 배열을 만들어야 하기 

때문에 상대적으로 공간 복잡도가 높지만, 조건만 맞다면 다른 방법보다 더 효율적인 알고리즘이다

 

계수 정렬은 데이터를 정수 형태로 표현할 수 있을 때 사용 가능하다.

계수 정렬은 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 크기의 리스트를 선언해야 한다

 

 

 

 

 

 

 

계수 정렬 코드에서 중첩 for문을 보면 바깥쪽 for문이 K 번 돌아가고 안쪽 for문은 수행 횟수가 N 번이므로 
시간복잡도는 O(K + N) 이다 

 

계수정렬은 동일한 값을 가지는 데이터가 여러 개 나올 때 효과적이다.