우리는 약간 m> 0이 있고, 알고리즘은 시간 O에서 N^m -1 (MN)의 범위 0 N 정수 정렬 제공해야하는 경우. 나의 제안은 다음과 같습니다기수 정렬 런타임
Radix-Sort(A,t) // t is the digit length
for i=0 to t
do Insertion-Sort A on digit i
내 인수가 그 위의 실행에서 O (백만) 때문에 각 숫자 t에 대해 - 각 실행에 대한 범위가 작기 때문에 삽입 정렬은 O (n)의 시간이 소요됩니다.
올바른 제안입니까? 위의 공간 요구 사항은 무엇이되어야합니까?
감사합니다.
n 개의 항목을 배치하려면 원래 숫자와 m 버킷이 있어야하므로 공간 요구 사항은 O (m + n)입니다. 런타임은 O (mn)이며 >> n이 될 수 있습니다. 이는 기수 정렬과 관련된 문제입니다. 모든 경우에 O (mn)하지만 문제는 m> n 인 경우 O (n^2)보다 큰 값을 얻는 것입니다. 작성 방법에 따라 정렬 할 n 개의 숫자 세트의 m 개의 사본을 작성하기 때문에 메모리가 최악의 경우 O (mn) 일 수도 있습니다.
Counting sort을 사용하면 작은 범위의 이산 숫자를 정렬 할 때 데이터 크기와 범위에 대한 검색의 선형성을 보장 할 수 있습니다 (삽입 정렬은 O(n^2) 최악의 경우의 복잡도로 비교 정렬 임). , 데이터가 잘못된 방향으로 정렬 된 경우 작은 범위는 삽입 요소 정렬에 도움이되지 않습니다. 모든 요소가 이동되기 때문입니다.
카운팅 정렬을 사용할 때 공간의 복잡도는 O(n+k)입니다. 여기서 n은 배열의 크기이고 k는 데이터의 범위입니다. 원시 데이터를 정렬하기 때문에 동일한 배열을 사용하여 결과를 정렬하고 반환 할 수 있습니다.