숫자의 작은 범위에서 계산 정렬을 수행 할 수 있습니까? 거대한 숫자 풀에서 A = [7,9,12,15]라고 말하면됩니다. 작은 배열의 숫자만으로 구성됩니다. 또는 작은 범위는 항상 [0..k]이어야합니다.정렬 범위의 계산은 항상 [0, k]에 있어야합니까?
[0..15]라고 말하면 배열 A에 대해 계산할 수 있지만 의미가 없습니다. 그리고 A = [100,750,452]
그래서 나는 그것이 가능하다고 생각합니다. 몇 가지 의견을 부탁드립니다.
귀하의 질문은 명확하지 않지만 여기에 있습니다. 귀하의 예제에서 A = [7,9,12,15] 범위는 [0..15]이고 크기 k = 15의 추가 공간과 A [길이]의 또 다른 결과 배열이 필요합니다 .n (A [길이 ])가 4 일 때, 전체 런타임은 theta (k + n)가 될 것입니다. 카운팅 정렬은 "시공간 트레이드 오프"입니다. 그러나 당신의 경우에 사용된다면 아무런 의미가 없습니다. 당신의 A []의 최대 값이 A []의 크기보다 작다는 것을 의미하는 k = Big-O (n) 일 때 계산 방식을 사용해야합니다. btw, 나는 알고리즘이 당신의 예제를 여전히 정렬한다고 믿습니다. 올바르게.