방금 Bucket sort에 관한 위키 백과 페이지를 읽었습니다. 이 기사에서 그들은 최악의 경우의 복잡성은 O (n²)라고 말합니다. 하지만 최악의 경우 복잡성은 O (n + k)라고 생각했습니다. 여기서 k는 버킷의 개수입니다. 이것이 내가이 복잡성을 계산하는 방법입니다.버킷 정렬의 최악의 복잡성은 무엇입니까?
- 요소를 버킷에 추가합니다. (1) 리스트 거치지
- 올바른 버킷의 요소를 넣어 = O (n)은 버킷 병합
- = O (K)
- O (1) * O이 O 인 링크 된리스트를 사용하여 (n) + O (k) = O (n + k)
나는 뭔가를 놓친가요?
필연적으로, 항상 'O (1)'성능을 제공하는 목록의 앞부분에 추가 할 수 있습니다. 그러나, 어느 쪽이든 최악의 경우'O (n^2) '성능의 출처 인 개별 물통을 결국 * 정렬 *해야합니다. – smessing
내 대답은 단순화 된 것입니다. 목록의 맨 앞에 추가하지 말아야합니다. 편집에서 추가 할 내용이 있습니다. – mfrankli
이것은 제 이해입니다. 그러나 저는 100 % 확신하지 못합니다 : 해답은 bucket-sort가 비교 기반 정렬에 대한 nlogn 하한값을 향상시키기위한 시도라는 사실에서 비롯됩니다. 목록의 맨 앞에 추가하면 각 버킷 내에서 정렬해야합니다. 그러면 비교 기반 정렬의 nlogn 상한/하한 경계로 되돌아갑니다. 그래서 bucket-sort는 요소를 순서대로 버켓에 넣기를 원합니다. 평균적인 경우에, 이것은 모두 좋고 좋습니다. 그러나 nlogn을 이길 시도에서이 최악의 경우가 나타납니다. 이 사실을 누구도 확인할 수 있습니까? – mfrankli