Czy Quicksort zawsze ma kwadratowy czas działania, jeśli jako element przestawny wybierzesz maksymalny element?

9

Jeśli masz algorytm szybkiego sortowania i zawsze wybierasz najmniejszy (lub największy) element jako element przestawny; czy mam rację zakładając, że jeśli dostarczysz już posortowany zestaw danych, zawsze uzyskasz najgorsze wyniki niezależnie od tego, czy twoja „już posortowana” lista jest w porządku rosnącym czy malejącym?

Myślę, że jeśli zawsze wybierzesz najmniejszy element dla swojego elementu przestawnego, to to, czy Twoje „już posortowane” dane wejściowe są sortowane według rosnącego czy malejącego, nie ma znaczenia, ponieważ podzbiór wybrany do sortowania względem twojego elementu przestawnego zawsze będzie ten sam rozmiar?

— yoonsi
źródło

2

Twoje myślenie jest poprawne, ale w tym przypadku możesz również kłócić się bezpośrednio i obliczyć czas działania Quicksort - otrzymasz .

O (n^{2})

$O(n^2)$

— Yuval Filmus,

15

W najgorszym przypadku złożoność szybkiego sortowania to . Osiąga się to poprzez wybieranie osi przestawnych, które dzielą zestaw tak, że jedna grupa ma tylko jednego członka. Przy złym algorytmie pobierania osi obrotowej można to łatwo osiągnąć, wybierając jeden koniec posortowanego zestawu. Twoje założenie jest prawidłowe. $\Theta(n^2)$

— walrii
źródło

2

Lepiej było napisać: „... Osiąga się to przez wybranie elementów przestawnych, które dzielą zestaw tak, że jedna grupa ma tylko członka O (1)”

@ Saeed Amiri: Zgadza się, ale lepiej być precyzyjnym.

— MMS

1

@ SaeedAmiri: O (1) wskazuje, że jest on proporcjonalny do 1, co oznacza, że może być k * 1. Rzeczywisty najgorszy przypadek osiąga się, gdy wynosi dokładnie 1. Zapewniam cię, że O (1) może nadal prowadzić do O (n ^ 2).

— walrii

@MMS, a konkretnie napisałem , walrii Napisałeś: „Najgorszy przypadek złożoności dla szybkiego sortowania to ..”, ale tak naprawdę jedyny sposób na osiągnięcie nie jest tym, co powiedziałeś, tak, jak opisałeś, jest najgorszym ze wszystkich przypadków, ale nie jedynym .

O (1)

$O(1)$

Θ (n^{2})

$\Theta (n^2)$

Θ (n^{2})

$\Theta(n^2)$

Θ (n^{2})

$\Theta (n^2)$

5

Tak! Myślisz, że ma absolutną rację! Jak słusznie wspomniał Yuval Filmus, czas działania wyniesie $\Theta(n^2)$

— n0nChun
źródło

3

Jedna podtablica będzie miała lub element, podczas gdy druga będzie miała elementy; stąd jest : $0$ $1$ $(n-1)$ $O(n^2)$

t (n) = t (n - 1) + t (0) + O (n) = O (n^{2})

$t(n)=t(n-1)+t(0)+O(n)= O(n^2)$

— sulava
źródło