Jaka jest najgorsza złożoność sortowania kubełków?

Question

Właśnie przeczytałem stronę Wikipedii o Bucket sort. W tym artykule mówią, że najgorszym przypadku złożoność jest O (n²). Ale myślałem, że najgorszym przypadku złożoności był O (n + k), gdzie k to liczba wiaderek. Oto, jak obliczam tę złożoność:

1. Dodaj element do wiadra. Za pomocą połączonego LISTY O (1)
2. Przechodząc przez liście i umieszczenie elementów w odpowiedniej wiadra = O (n)
3. Połączenie wiadra = O (K)
4. O (1) * O (n) + O (k) = O (n + k)

Czy czegoś brakuje?

Answer 1

Co się stanie, jeśli algorytm zdecyduje, że każdy element należy do tego samego zasobnika? W takim przypadku połączona lista w tym zasobniku musi być przesuwana za każdym razem, gdy element jest dodawany. To wymaga 1 kroku, potem 2, potem 3, 4, 5 ... n. Zatem czas jest sumą wszystkich liczb od 1 do n, która jest (n^2 + n)/2, która jest O (n^2).

Oczywiście jest to "najgorszy przypadek" (wszystkie elementy w jednym wiadrze) - algorytm służący do obliczenia, które wiadro na miejsce elementu ma na ogół na celu uniknięcie tego zachowania.

Answer 2

Aby scalić wiadra, najpierw trzeba je posortować. Rozważmy Pseudokod podaną w artykule Wikipedii:

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] 

The nextSort(buckets[i]) rodzaje każdego z poszczególnych wiadrach. Ogólnie rzecz biorąc, sortowanie wiader jest sortowane według innego rodzaju sortowania (np. Sortowanie wtrącone), ponieważ po zmniejszeniu i rozmiarze różne, nierekurencyjne rodzaje często dają lepszą wydajność.

Rozważ teraz przypadek, w którym wszystkie elementy n znajdą się w tym samym pojemniku. Jeśli użyjemy sortowania w celu sortowania pojedynczych segmentów, może to prowadzić do najgorszego przypadku: O(n^2). Myślę, że odpowiedź musi być zależna od rodzaju sortowania poszczególnych wiader.

Answer 3

Jeśli możesz zagwarantować, że każde wiadro reprezentuje unikalną wartość (elementy równoważne), wtedy złożoność najgorszego przypadku wynosiłaby O (m + n), jak wskazałeś.

Answer 4

Sortowanie kubełkowe zakłada, że ​​dane wejściowe są rysowane z jednolitego rozkładu. Oznacza to, że w każdym wiadrze znajduje się kilka przedmiotów. To z kolei prowadzi do ładnego średniego czasu działania O (n). Rzeczywiście, jeśli n elementów zostanie wstawionych do każdego kubełka, tak aby elementy O (1) wpadały do ​​każdego innego kubła (wkładanie wymaga O (1) na element), to sortowanie wiadra przy użyciu sortowania wstawek wymaga średnio O (1) również (co udowodniono w prawie wszystkich podręcznikach dotyczących algorytmów). Ponieważ musisz sortować n wiader, średnia złożoność to O (n).

Załóżmy teraz, że dane wejściowe nie pochodzą z jednolitego rozkładu. Jak już wskazano przez @mfrankli, może to w najgorszym przypadku doprowadzić do sytuacji, w której wszystkie przedmioty upaść na przykład w pierwszym wiadrze. W takim przypadku sortowanie wstawek będzie wymagało w najgorszym przypadku O (n^2).

Zauważ, że możesz użyć poniższej sztuczki, aby utrzymać tę samą średnią złożoność O (n), jednocześnie zapewniając złożoność O (n log n) w najgorszym przypadku.Zamiast używać sortowania wstawiania, po prostu użyj algorytmu o złożoności O (n log n) w najgorszym przypadku: albo sortowanie scalone, albo sortowanie sterty (ale nie sortowanie szybkie, które tylko średnio osiąga O (n log n)).

Answer 5

To jest odpowiedź do dodatku @perreal. Próbowałem opublikować to jako komentarz, ale jest zbyt długi. @perreal prawidłowo wskazuje, kiedy sortowanie wiadra ma największy sens. Różne odpowiedzi przyjmują różne założenia dotyczące tego, jakie dane są sortowane. NA PRZYKŁAD. jeśli klucze do posortowania są łańcuchami, to zakres możliwych kluczy będzie zbyt duży (większy niż tablica kubełkowa), a będziemy musieli używać tylko pierwszego znaku ciągu dla pozycji kubełka lub innej strategii. Poszczególne segmenty będą musiały być posortowane, ponieważ zawierają elementy z różnymi kluczami, co prowadzi do O (n^2).

Ale jeśli sortujemy dane, w których klucze są liczbami całkowitymi w znanym zakresie, to segmenty są zawsze sortowane, ponieważ klucze w wiadrze są równe, co prowadzi do liniowego sortowania czasu. Nie tylko sortuje się wiadra, ale sortuje się, ponieważ możemy wyciągnąć elementy z tablicy kubełków w kolejności, w jakiej zostały dodane.

Rzeczą, którą chciałem dodać, jest to, że jeśli masz do czynienia z O (n^2) ze względu na naturę kluczy do posortowania, sortowanie kubełkowe może nie być właściwym podejściem. Gdy masz zakres możliwych kluczy proporcjonalny do rozmiaru wejścia, możesz skorzystać z liniowego sortowania kubełków czasowych, ponieważ każdy zasobnik ma tylko jedną wartość klucza.