버킷 정렬의 최악의 복잡성은 무엇입니까?

Question

방금 ​​Bucket sort에 관한 위키 백과 페이지를 읽었습니다. 이 기사에서 그들은 최악의 경우의 복잡성은 O (n²)라고 말합니다. 하지만 최악의 경우 복잡성은 O (n + k)라고 생각했습니다. 여기서 k는 버킷의 개수입니다. 이것이 내가이 복잡성을 계산하는 방법입니다.

1. 요소를 버킷에 추가합니다. (1)
리스트 거치지
2. 올바른 버킷의 요소를 넣어 = O (n)은 버킷 병합
3. = O (K)
4. O (1) * O이 O 인 링크 된리스트를 사용하여 (n) + O (k) = O (n + k)

나는 뭔가를 놓친가요?

Answer 1

알고리즘이 모든 요소가 동일한 버킷에 속한다고 판단하면 어떻게 될까요? 이 경우 요소가 추가 될 때마다 해당 버킷의 연결된 목록을 탐색해야합니다. 1 단계 걸린 다음 2, 3, 4, 5 ... n. 따라서 시간은 1에서 n까지의 숫자의 합계이며, 이는 (n^2 + n)/2이며 O (n^2)입니다.

물론 이것은 "최악의 경우"(하나의 버킷에있는 모든 요소)입니다. 요소를 배치 할 버킷을 계산하는 알고리즘은 일반적으로 이러한 동작을 피하기 위해 설계되었습니다.

Answer 2

버킷을 병합하려면 먼저 버킷을 정렬해야합니다.

function bucketSort(array, n) is 
    buckets ← new array of n empty lists 
    for i = 0 to (length(array)-1) do 
    insert array[i] into buckets[msbits(array[i], k)] 
    for i = 0 to n - 1 do 
    nextSort(buckets[i]) 
    return the concatenation of buckets[0], ..., buckets[n-1] 

nextSort(buckets[i]) 종류의 개별 버킷의 각 : 위키 백과의 문서에서 주어진 의사를 생각해 보자. 일반적으로 다른 정렬을 사용하여 버킷을 정렬합니다 (삽입 정렬). 한 번 내려서 크기를 지정하면 다른 재귀 적 정렬을 사용하면 성능이 향상 될 수 있습니다.

이제 모든 n 요소가 같은 버킷으로 끝나는 경우를 생각해보십시오. 삽입 정렬을 사용하여 개별 버킷을 정렬하는 경우 최악의 경우 성능이 O(n^2)이 될 수 있습니다. 그 대답은 개별 버켓을 분류하기 위해 선택한 종류에 따라 달라져야한다고 생각합니다.

Answer 3

각 버킷이 고유 한 값 (동등한 항목)을 나타낼 수 있다면 최악의 경우의 시간 복잡도는 사용자가 지적한대로 O (m + n)가 될 것입니다.

Answer 4

버켓 정렬은 입력이 일정한 분포에서 나온 것으로 가정합니다. 이는 몇 가지 항목이 각 버켓에 있음을 의미합니다. 결과적으로 O (n)의 좋은 평균 실행 시간이됩니다. 사실 O (1) 요소가 각기 다른 버킷 (삽입은 항목 당 O (1)이 필요함)에 속하도록 n 개의 요소가 각 버킷에 삽입 된 경우 삽입 정렬을 사용하여 버킷을 정렬하려면 평균적으로 O (1) (이것은 알고리즘에 관한 거의 모든 교과서에서 증명되었습니다). 버킷을 정렬해야하므로 평균 복잡도는 O (n)입니다.

이제 입력이 일정한 분포에서 나오지 않는다고 가정하십시오. @mfrankli에 의해 이미 지적 되었 듯이, 이것은 최악의 경우 모든 항목이 예를 들어 첫 번째 버킷에 모두 들어간 상황을 초래할 수 있습니다. 이 경우 삽입 정렬은 최악의 경우 O (n^2)가 필요합니다.

최악의 경우 O (n log n) 복잡성을 제공하면서 동일한 평균 O (n) 복잡성을 유지하려면 다음 트릭을 사용할 수 있습니다.삽입 정렬을 사용하는 대신 최악의 경우에 O (n log n) 복잡도를 갖는 알고리즘을 사용하십시오 : 병합 정렬 또는 힙 정렬 (빠른 정렬이 아니고 O (n log n)이 평균적으로 만 이루어짐).

Answer 5

이것은 @perreal의 부가 기능 응답입니다. 내가 코멘트로 게시하려고했지만 너무 깁니다. 버킷 정렬이 가장 의미가있을 때 @perreal이 올바르게 지적하고 있습니다. 다른 답변은 어떤 데이터가 정렬되는지에 대해 서로 다른 가정을하고 있습니다. E.G. 정렬 할 키가 문자열 인 경우 가능한 키의 범위가 너무 커서 (버킷 배열보다 큼), 버킷 위치 또는 다른 전략에 대해 문자열의 첫 번째 문자 만 사용해야합니다. 개별 버킷은 다른 키가있는 항목을 보유하므로 O (n^2)로 정렬해야 정렬됩니다.

그러나 키가 알려진 범위의 정수 인 데이터를 정렬하는 경우 양동이의 키가 동일하므로 선형 시간 소트가 발생하므로 버킷은 항상 정렬됩니다. 버킷은 정렬되어있을뿐만 아니라 종류가 입니다. 추가 된 순서대로 버킷 배열에서 항목을 가져올 수 있기 때문입니다.

내가 추가하고 싶은 것은 정렬 할 키의 특성 때문에 O (n^2)를 향하고 있다면 버킷 정렬이 올바른 접근 방식이 아닐 수도 있다는 것입니다. 입력 크기에 비례하는 가능한 키 범위가 있으면 각 버킷에 키 값 하나만 보유하도록 선형 시간 버킷 정렬을 활용할 수 있습니다.