Najlepsze i gorsze dane wejściowe do sortowania sterty i szybkiego sortowania?

sterta – ponieważ najlepszy i najgorszy przypadek jest taki sam czy to nie ma znaczenia kolejność wprowadzania? Liczba porównań i przypisań zawsze będzie taka sama? Wyobrażam sobie, że w sortowaniu sterty może być tak samo, ponieważ prawdziwa praca jest wykonywana we wstawianiu, ale sortowanie wykorzystuje tylko usunięcie max / min sterty? Czy to dlatego?

Liczba wykonanych porównań faktycznie może zależeć od kolejność, w jakiej podano wartości. Fakt, że najlepszy i najgorszy przypadek to Θ (n log n) – zakładając, że wszystkie elementy są różne – oznacza tylko, że asymptotycznie nie ma różnicy między nimi, chociaż mogą różnić się stałym czynnikiem. Nie mam na to prostych przykładów, ale uważam, że można konstruować dane wejściowe, w których liczba porównań różni się o stałą wartość między dwa podejścia. Ponieważ notacja duże-O ignoruje jednak stałe, nie jest to odzwierciedlone w analizie najlepszego i najgorszego przypadku.

szybkie sortowanie. Nie wiem na pewno. Nie jestem pewien, jaki jest najlepszy i najgorszy przypadek w tym przypadku. Jeśli na przykład jest to już posortowana lista 10 ciągów, czy nie zawsze musimy wybierać taką samą liczbę przestawnych, aby ukończyć algorytm rekurencyjny? Każda pomoc dotycząca tego wyjaśnienia byłaby naprawdę pomocna.

Liczba wybranych przestawnych jest rzeczywiście taka sama, niezależnie od wykonania algorytmu. Jednak praca wykonana dla każdego obrotu może się różnić w zależności od rodzaju uzyskanych podziałów. W najlepszym przypadku obrót wybrany w każdym kroku kończy się jako środkowy element tablicy. Kiedy tak się dzieje, jest (w przybliżeniu) n porównań wykonanych w górnej warstwie rekurencji, a następnie (w przybliżeniu) n na następnej warstwie, ponieważ istnieją dwie podtablice o rozmiarze n / 2, a następnie (w przybliżeniu) n w następnej warstwa, ponieważ istnieją cztery podtablice o rozmiarze n / 4 itd. Ponieważ istnieją warstwy Θ (log n), a każda warstwa ma Θ (n) praca, całkowita wykonana praca to Θ (n log n). Z drugiej strony rozważ wybranie absolutnego minimum każdej tablicy jako przestawnej. Następnie (z grubsza) wykonuje się n porównań w górnej warstwie, następnie (z grubsza) n – 1 w następnej warstwie, następnie (z grubsza) n – 2 w następnej itd. Suma 1 + 2 + 3 + … + n wynosi Θ (n ² ), stąd najgorszy przypadek.

Mam nadzieję, że to pomoże!

Komentarze

• Proszę pana, jak najlepiej zastosować heapsort nlogn? Jeśli weźmiemy pod uwagę wszystkie elementy są identyczne, koszt byłby po prostu iteracją przez wszystkie elementy tablicy i bez przechodzenia w górę do korzenia. Więc według mnie powinno to być omega (n).
• To dobra uwaga. Zakładałem różne elementy, więc zaktualizuję tę odpowiedź.

Ponieważ nikt nie jest naprawdę zaadresowano heapSort:

Zakładając, że „używasz maksymalnego stosu reprezentowanego jako tablica i wstawiasz swoje max elementów wstecz do tablicy wyjściowej / z tyłu tablicy, jeśli robisz to na miejscu” , w najgorszym przypadku dane wejściowe dla heapSort to dowolne dane wejściowe, które zmuszają Cię do „bąbelkowania” lub ponownego zestawiania za każdym razem, gdy usuwasz element. Dzieje się tak za każdym razem, gdy próbujesz sortować zestaw bez duplikatów. Nadal będzie to Θ (n log n), jak powiedział templatetypedef.

Ta właściwość implikuje, że najlepszym przypadkiem heapSort jest sytuacja, gdy wszystkie elementy są równe (Θ (n), ponieważ nie musisz ponownie obliczać kosztów po każdym usunięciu, co zajmuje log (n) czasu od maksymalna wysokość sterty to log (n)). To trochę kiepski / niepraktyczny przypadek, dlatego najlepszym rozwiązaniem dla sortowania stert jest Θ (n log n).

Komentarze

• Twój punkt widzenia na ten kiepski, niepraktyczny przypadek został właśnie zadany na moich zajęciach z algorytmów. (uważaj na podchwytliwe pytania). Oczywiście ' nadal zgadzam się z twoim punktem ( i otrzymałem błędną odpowiedź XD)

• Szybkie sortowanie

  Najgorszy przypadek: $ \ mathcal {O} (n ^ 2) $ . Załóżmy, że element przestawny jest zawsze najbardziej po prawej stronie: wprowadź już posortowana lista z elementami $ n $ . Każde partycjonowanie prowadzi do jednej listy z elementami $ n-1 $ i jedną listę z elementami $ 0 $ . Nawet jeśli wybierzesz element pivot losowo , nadal możesz mieć pecha i zawsze wybieraj maksymalną wartość z listy.

  Niech $ T (n) $ będzie liczbą porównań quicksort wymaga sortowania listy zawierającej elementy $ n $ . Najgorszy przypadek: \ begin {align} T (n) = & T (n-1) + n & \ text {($ T (n-1) $ recursive, $ n $ to partion)} \\ = & \ frac {n (n + 1) } {2} \ in \ mathcal {O} (n) \ end {align}

  Najlepszy przypadek: $ \ mathcal {O} (n \ log n) $ . Jeśli element pivot jest wybrany w taki sposób, że dzieli listę równo na partycje:

  \ begin {align} T (n) = & 2 \ T \ left (\ frac {n} {2} \ right) + n & (\ text {2 razy $ \ frac {n} { 2} $ recursive, $ n $ to partycja)} \\ \ in & \ mathcal {O} (n \ log n) & (\ text {główne twierdzenie}) \ end {align}

• Sortowanie na stosie

  Najgorszy przypadek i najwyższa złożoność wielkości liter dla sortowania na stosie to $ \ mathcal {O} (n \ log n) $ . Dlatego sortowanie na stosie wymaga $ \ mathcal {O} (n \ log n) $ porównań dla dowolnej tablicy wejściowej. Złożoność sortowania na stosie:

  \ begin {align} & \ mathcal {O} (n) & (\ text {build $ (1, n) $ heap}) \\ + & \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i – \ log 1) & (\ text {build $ (1, j) $ heap}) \\ = & \ mathcal {O} (n) + \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i) & (\ tekst {reguła ilorazu logarytmów}) \\ = & \ mathcal {O} (n \ log n) & \ left (\ sum_ {i = 1} ^ {n} \ log i < \ sum_ {i = 1} ^ {n} \ log n = n \ log n \ right) \ end {align }

Komentarze

• Nie masz ' t odpowiedziałem na wszystkie pytania OP ', więc odpowiem na jedno, które przegapiłeś; sortowanie stosu nie ' nie zawsze używa tej samej liczby porównań dla danej liczby elementów. Najgorszy przypadek to $ a \, n \ log n $, a najlepszy to $ b \, n \ log n $, gdzie $ a > b $.
• Należy również pamiętać, że wariant trójdrożny ma liniowy przypadek w przypadku wprowadzania pojedynczego elementu.