Próbowanie zrozumienia 2N lnN porównuje dla szybkiego sortowania

13

Analizowałem szybkie sortowanie w książce Algorytmy Sedgewicka. Tworzy następującą relację powtarzalności dla liczby porównań w szybkim sortowaniu podczas sortowania tablicy N różnych elementów.

wprowadź opis zdjęcia tutaj

Trudno mi to zrozumieć ... Wiem, że potrzeba 1 / N prawdopodobieństwa, aby każdy element stał się osią obrotu i że jeśli k stanie się osią obrotu, wówczas lewa pod-tablica będzie miała elementy k-1 i prawe pod- tablica będzie miała elementy Nk.

1.Jak koszt partycjonowania staje się N + 1? Czy wykonanie partycjonowania wymaga porównania N + 1?

2.Sedgewick mówi, że dla każdej wartości k, jeśli dodasz te wartości, prawdopodobieństwo, że elementem partycjonującym jest k + koszt dwóch pod-macierzy, otrzymasz powyższe równanie.

  • Czy ktoś może to wyjaśnić, aby osoby o mniejszej wiedzy matematycznej (ja) mogły to zrozumieć?
  • W szczególności, w jaki sposób otrzymujesz drugi człon w równaniu?
  • Co dokładnie oznacza ten termin?
Damon
źródło
1
Część odpowiedzi, skopiowana z en.wikipedia.org/wiki/Quicksort "Tak więc uśrednianie wszystkich możliwych podziałów i zauważanie, że liczba porównań dla partycji wynosi n - 1, średnia liczba porównań dla wszystkich permutacji danych wejściowych sekwencję można dokładnie oszacować, rozwiązując relację nawrotu: „Z jakiegoś powodu jesteśmy tutaj wyłączeni o 2 - n-1 vs n + 1.
Job

Odpowiedzi:

7

Funkcja kosztu Cdla Quicksort składa się z dwóch części. Pierwsza część to koszt podzielenia tablicy na dwie „połówki” (połówki nie muszą być równej wielkości, stąd cytaty). Druga część to koszt sortowania tych dwóch połówek.

  1. (N + 1)Termin jest rzeczywiście skrócone określenie i pochodzi z warunkami

    (N - 1) + 2
    

    Jest to koszt partycjonowania w szybkim sortowaniu: N-1porównuje z wartością przestawną, a 2 dodatkowe porównuje ze względu na pewne warunki brzegowe w partycjonowaniu.

  2. Druga część równania składa się z kosztów sortowania dwóch „połówek” po obu stronach wartości obrotu k.

    Po wybraniu wartości przestawnej pozostają dwie nieposortowane „połówki”. Koszt sortowania tych „połówek” zależy od ich wielkości i jest najłatwiej opisany jako rekurencyjne zastosowanie funkcji kosztu C. Jeśli oś przestawna jest najmniejszą z Nwartości, koszty sortowania każdej z dwóch „połówek” wynoszą odpowiednio C(0)i C(N-1)(koszt sortowania tablicy z 0 elementami i koszt sortowania jednej z N-1elementami). Jeśli oś jest piątą najmniejszą, wówczas koszt sortowania każdej z dwóch „połówek” wynosi odpowiednio C(5)i C(N-6)(koszt sortowania tablicy z 5 elementami i koszt sortowania jednej z N-6elementami). I podobnie dla wszystkich innych wartości przestawnych.

    Ale ile kosztuje sortowanie tych dwóch „połówek”, jeśli nie znasz wartości przestawnej? Odbywa się to poprzez pobranie kosztu każdej możliwej wartości osi obrotu i pomnożenie tego przez szansę, że ta konkretna wartość się pojawi.

    Ponieważ każda wartość przestawna jest jednakowo prawdopodobna, szansa na wybranie określonej wartości przestawnej jest, 1/Njeśli masz Nelementy. Aby to zrozumieć, pomyśl o rzuceniu kostką. Przy odpowiednich kostkach szansa, że ​​każda strona skończy odkryta, jest równa, więc szansa na wyrzucenie 1 wynosi 1/6.

    W połączeniu daje to sumę, w której dla każdej możliwej wartości k elementu przestawnego koszt ( C(k-1) + C(N-k)) jest mnożony przez szansę ( 1/N)

  3. Dalsze wyprowadzenie formuły sumowania w pytaniu do 2N lnNtytułu zajmuje zbyt wiele matematyki, aby wyjaśnić tu szczegóły, ale opiera się na zrozumieniu, że koszt sortowania tablicy Nelementów ( C(N)) można wyrazić w kategoriach sortowania tablica N-1elementów ( C(N-1)) i współczynnik, który jest wprost proporcjonalny do N.

Bart van Ingen Schenau
źródło
2
  1. Wydaje się, że N + 1 jako liczba porównań dla etapu podziału jest błędem w książce. Musisz dowiedzieć się, dla każdego z elementów N-1 niepodzielnych, czy jest on mniejszy czy większy niż element przestawny, co wymaga jednego porównania; zatem porównania N – 1 łącznie, a nie N + 1. (Rozważmy najprostszy przypadek, N = 2, tj. Jeden punkt obrotu i jeden inny element: absolutnie nie ma miejsca na trzy porównania między dwoma elementami.)

  2. Rozważ przypadek, w którym wybrany element obrotowy jest najmniejszym elementem (k = 1). Oznacza to, że tablica jest podzielona na pustą część po lewej stronie (nie ma elementów mniejszych niż oś obrotu) i część po prawej stronie, która zawiera wszystkie elementy oprócz osi obrotu (wszystkie inne elementy są większe niż oś obrotu) ). Oznacza to, że pod-problemy, które teraz chcesz rozwiązać rekurencyjnie, mają odpowiednio rozmiary 0 i N – 1 (k – 1 i N – k) i wymagają porównań C (0) i C (N – 1); zatem C (0) + C (N – 1) ogółem.

    Jeśli oś jest przypadkiem drugim najmniejszym elementem (k = 2), rozmiary podproblemów to 1 i N – 2 (k – 1 i N – k; jeden element po lewej stronie, ponieważ jest on jedyny mniejszy niż oś). Zatem rekurencyjne rozwiązanie tych podproblemów wymaga porównań C (1) + C (N – 2). I tak dalej, jeśli oś jest trzecim najmniejszym elementem, czwartym itd. Są to wyrażenia w licznikach.

    Ponieważ oś jest wybierana losowo spośród N elementów, każdy przypadek (oś jest najmniejsza, oś jest druga najmniejsza itd.) Występuje z jednakowym prawdopodobieństwem 1 / N. Stąd pochodzi N w mianownikach.

Chirlu
źródło