정렬 계산의 시간 복잡도

Question

알고리즘 과정을 거치며 정렬 계산의 시간 복잡도가 O (n + k) 인 것을 보았습니다. 여기서 k는 숫자의 범위이고 n은 입력 크기입니다. 내 질문은 k = 0 (n) 또는 O (n)와 같이 k와 n의 차이가 너무 큰 경우 복잡성을 O (n)라고 말할 수 있습니까? 또는 O (n)? 그렇다면이 경우 카운팅 정렬은 현명한 접근법이 아니며 병합 정렬을 사용할 수 있습니다. 내가 맞습니까?

Answer 1

예, 당신은 모든 카운트에서 정확합니다.

한층 더 강하게 문을 만들 수있다 : 때 K = O를 (N ²) 또는 (N ³) O, 우리가 계산 정렬의 복잡도는 Θ라고 말할 수 (N ²) 또는 Θ (n).

Answer 2

이론적으로 O (n) 시간으로 정렬 할 수 있습니다. 값의 범위가 1 ~ n 이면 기본 n으로 변환하고 기수 정렬을 수행합니다. 기본 n에서 숫자는 3 자리 숫자이므로 실행 시간은 기본 변환의 O (3n + 3n) + O (n)입니다. 전반적인 O (n).