기수 정렬 - O (n) 시간

Question

n 개의 숫자를 정렬하고 정렬되는 숫자가 기본 n으로 변환 된 경우 O (n) 시간에 기수 정렬을 수행 할 수 있다고 들었습니다.

이 권리가 있습니까?

그렇다면 정확하게 달성되는 방법입니다. 우리가 5 개의 숫자를 다루고 그것들을 모두 밑으로 5로 변환한다면, 숫자를 5 개의 버킷 (0, 1, 2, 3, 4)으로 분리 할 수 ​​있습니다.

비록 우리가 다루고있는 숫자가 최대 7 자리수 일지라도, 적어도 7 * 5 번 반복해야만합니까? 그러나 이것은 옳지 않은 것처럼 보입니다. 그러나.

죄송합니다. 혼란 스럽습니다.

도움 주셔서 감사합니다.

Answer 1

기수 정렬은 기수 b를 선택하고 기수 b의 모든 입력을 기초 b로 작성한 다음 한 번에 한 자리 씩 숫자를 정렬하여 작동합니다. 이 대답에서는, 최하위 자리, 그 다음 두 번째 최하위 자리 등 모든 것을 정렬하는 최하위 자리 기수 정렬에 초점을 맞 춥니 다.

일부 숫자는 모든 버킷에서 요소를 배포하기 위해 O (n) 작업을 수행 한 다음 O (n + b)가 버킷에서 반복하고 정렬 된 순서로 요소를 가져와야합니다. 따라서 하나의 기수 정렬에 대한 런타임은 O (n + b)입니다.

기수 순열의 수는 각 숫자의 자릿수에 따라 다릅니다. 기수 b에 숫자를 쓰는 경우 숫자 M에 O (로그 _b M)의 b 자릿수가 표시됩니다. M을 입력 배열의 최대 수로 나타내면 기수 순의 순환 수가 O 일 것 (로그 _b M). 따라서 기수 정렬의 점근 적 런타임은

O (n + b) & middot; O (로그 _bM) = O ((n + b) log _bM).

일반적인 이진 기수 정렬에서는 b = 2를 선택하고 O (n log M)의 런타임을 얻습니다. 그러나 b를 원하는 모든 값으로 선택할 수 있습니다. 더 큰 b 값을 선택하면 각 숫자에 더 적은 b 숫자가 생깁니다 (예를 들어, 밑 10과 밑 16에 숫자를 쓰면 대개 숫자가 적어집니다). base-16). 귀하의 원래 질문에서 귀하가 묻는 질문

우리가 다루고있는 숫자가 최대 7 자리수 일지라도, 적어도 7 * 5 번 반복해야합니까?

답변은 "필수적이지 않습니다." 7 자리 숫자로 기본 10 진수 정렬을 수행하면 예를 7 번 순환해야합니다. 그러나 기본 100 기수 정렬을 사용했다면 4 회 순환하면됩니다.

다른 질문은 기수 정렬에 base-n을 사용하는 것입니다.우리는 기본을 선택하면 우리는 N, 우리는 런타임

O ((N + N) _N M 로그) = O (N _N M 로그) 것을 얻을 수로 사용 = O (대수가 = _N M 로그 재기록 M/로그 N을 기록하는이 변화 수준의 기초 식을 사용)

를 (N M/로그 로그 n).

이것은 이 아니며이 아니며 기대해야합니다. 기수 정렬의 런타임은 정렬되는 문자열의 길이에 따라 다릅니다. 극히 소수의 극히 긴 숫자를 정렬하는 경우, 런타임은 소수의 작은 숫자를 정렬하는 시간보다 커야합니다. 왜냐하면 단순히 큰 숫자의 숫자를 읽어야하기 때문입니다. 기본 n을 사용하는 트릭은 알고리즘을 점근적으로 가속화하기위한 기술입니다.

희망이 도움이됩니다.