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.
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?
Odpowiedzi:
Funkcja kosztu
C
dla 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.(N + 1)
Termin jest rzeczywiście skrócone określenie i pochodzi z warunkamiJest to koszt partycjonowania w szybkim sortowaniu:
N-1
porównuje z wartością przestawną, a 2 dodatkowe porównuje ze względu na pewne warunki brzegowe w partycjonowaniu.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ą zN
wartości, koszty sortowania każdej z dwóch „połówek” wynoszą odpowiednioC(0)
iC(N-1)
(koszt sortowania tablicy z 0 elementami i koszt sortowania jednej zN-1
elementami). Jeśli oś jest piątą najmniejszą, wówczas koszt sortowania każdej z dwóch „połówek” wynosi odpowiednioC(5)
iC(N-6)
(koszt sortowania tablicy z 5 elementami i koszt sortowania jednej zN-6
elementami). 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/N
jeśli maszN
elementy. 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
)Dalsze wyprowadzenie formuły sumowania w pytaniu do
2N lnN
tytułu zajmuje zbyt wiele matematyki, aby wyjaśnić tu szczegóły, ale opiera się na zrozumieniu, że koszt sortowania tablicyN
elementów (C(N)
) można wyrazić w kategoriach sortowania tablicaN-1
elementów (C(N-1)
) i współczynnik, który jest wprost proporcjonalny doN
.źródło
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.)
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.
źródło