계산 및 기수 정렬의 실행 시간

Question

나는 계산 및 기수 정렬이 일반적으로 O (n) 시간에 실행되는 것으로 간주된다는 것을 알고 있으며 그 이유를 이해한다고 생각합니다. 그러나 나는 왜 이런 종류가 O (n) 시간에 분명하고 명백한 정수의리스트를 정렬하지 않을지를 설명하기 위해 과제를 요청 받고 있습니다. 나는 어떤 이유도 찾아 낼 수 없다.

도움을 주시면 감사하겠습니다.

Answer 1

계산 또는 기수 정렬이 O (n)이라고 말하는 것은 실제로 올바르지 않습니다.

Counting sort은 O (n + k)입니다. 여기서 k는 배열의 모든 요소의 최대 값입니다.

그 이유는 카운트 (O (n))를 채우기 위해 전체 목록을 단계별로 실행 한 다음 카운트 (O (k))를 단계별로 실행해야하기 때문입니다.

Radix sort은 O (mn)입니다. 여기서 m은 숫자의 최대 자릿수입니다.

이유는 각 숫자 (O (n) m 번)에 대해 한 번씩 배열을 단계적으로 이동해야하기 때문입니다.