시간 복잡성이 O (N) 인 정렬 알고리즘이 있습니까?

Question

대부분의 정렬 알고리즘은 결과를 얻기 위해 O (N N) 또는 O (N logN)의 복잡성을 갖습니다. 그러나 특정 입력 집합에 대해 O (N)의 복잡성을 갖는 알고리즘이 있습니다 .I 모든 경우에 O (N)의 복잡성을 갖는 정렬 알고리즘이 사용 가능한지 알고 싶습니다.

Answer 1

두 개의 항목이 <,>, ==) 인 경우에만 값을 비교하여 비교할 수 있다면 O (n log (n))보다 더 잘 수행 할 수 없습니다. 거기에있는 알고리즘에 대한 입증 된 하한선 중 하나입니다. 증거가 너무 복잡하지는 않습니다 (자세한 내용은 위키피디아의 비교 비교를 참조하십시오). 그러나 여기에서 반복하지 않아도됩니다.

비교가 아닌 다른 일을 할 수 있다면 유연성이 높아집니다. 숫자가있는 경우 버킷 정렬 (기수 정렬 유형)을 체크하면 O (n) 정렬이 가능합니다.

Answer 2

아니요. 가장 빠른 범용 정렬 알고리즘은 모두 O (nlgn)입니다. 실제로는 Θ (nlgn)입니다. 왜냐하면 비교 기반 정렬 알고리즘이 더 이상 효율적이지 못하다는 것이 수학적으로 입증 되었기 때문입니다.

다음은 비교 기반 정렬 알고리즘에서 찾은 문서입니다. http://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf

Answer 3

짧은 대답은 아니오입니다.

입력 배열의 각 요소가 유한 집합에 속하면 O (N) 알고리즘이 가능합니다. 입력이 항상 유한 집합 [0..9] 내에 있으면 말하십시오. 그런 다음 크기 10의 배열을 만들고 배열을 스캔하여 해당 인덱스를 증가시킬 수 있습니다.

그래서 모든 경우에 O (N) 정렬 알고리즘은 메모리가 무한 경우에만 가능합니다.