대부분의 정렬 알고리즘은 결과 를 얻기 위해 O (N N) 또는 O (N logN)의 복잡성을 가지고 있지만 특정 입력 집합에 대해 O (N)의 복잡성을 갖는 알고리즘이 있습니다. 모든 경우에 O (N)의 복잡성을 갖는 정렬 알고리즘이 있습니다.
정렬되는 값을 비교할 수만 있다면 (두 항목이 <,>, ==인지 확인), O (n log (n))보다 더 잘할 수 없습니다. 알고리즘에서 입증 된 몇 안되는 하한 중 하나입니다. 증명은 너무 복잡하지는 않지만 (자세한 내용은 위키피디아에서 비교 정렬을 확인하십시오) 여기서 반복하지 않을만큼 충분히 길다.
비교하는 것 외에 다른 것을 할 수 있다면 더 많은 유연성을 갖게됩니다. 숫자가있는 경우 버킷 정렬 (기수 정렬 유형)을 확인하면 O (n) 정렬이 가능합니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다