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

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?

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.

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.