Analiza sortowania przez wybieranie

Sortowanie przez wybór polega na przejściu przez kolejne pozycje w tablicy; dla każdej pozycji wywołuje indexOfMinimum, a następnie swap. Jeśli długość tablicy to n n , procedura ta zostanie powtórzona n n razy.
Ponieważ treść pętli składa się z dwóch linii kodu, może Ci się wydawać że w trakcie sortowania przez wybór zostanie wykonanych 2n 2 n linii kodu, lecz to nieprawda! Pamiętaj że indexOfMinimum i swap są funkcjami: wywołanie każdej z nich wiąże się z wykonaniem dodatkowych linii kodu.
Ile linii zostanie wykonanych przy wywołaniu swap? W najprostszej postaci będą to trzy linie, więc każde wywołanie swap wykona się w stałym czasie.
Ile linii kodu zostanie wykonanych dla pojedynczego wykonania indexOfMinimum? Musimy wziąć pod uwagę pętlę wewnątrz indexOfMinimum. Ile razy zostanie ona wywołana w pojedynczym wywołaniu indexOfMinimum? To zależy od rozmiaru podtablicy po której się iteruje. Jeśli podtablica obejmuje całą tablicę (jak w pierwszym kroku), treść pętli wykona się n n razy. Jeśli podtablica będzie miała rozmiar 6, treść pętli wykona się 6 razy.
Na przykład, powiedzmy że cała tablica ma rozmiar 8. Zastanówmy się jak zadziała sortowanie przez wybór.
  1. W pierwszym wywołaniu indexOfMinimum musi odwiedzić każdą wartość w tablicy więc treść pętli indexOfMinimum wykona się 8 razy.
  2. W drugim wywołaniu indexOfMinimum, funkcja musi odwiedzić każdą wartość w podtablicy na pozycjach 1 do 7, więc treść pętli w indexOfMinimum wykona się 7 razy.
  3. W trzecim wywołaniu, funkcja odwiedzi wartości w podtablicy na pozycjach 2 do 7, czyli pętla wykona się 6 razy.
  4. W czwartym wywołaniu zajmie się podtablicą na pozycjach 3 do 7, pętla wykona się 5 razy.
  5. W ósmym i ostatnim wywołaniu indexOfMinimum, pętla wykona się tylko raz.
Jeśli zliczymy wszystkie wykonania treści pętli w indexOfMinimum, otrzymamy 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 razy.

Dygresja: Wyliczanie sumy 1 do n n

Jak wyliczyć szybko sumę 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1? Oto sposób: Dodajmy wszystkie liczby w nietypowej kolejności. Najpierw, dodajmy 8 + 1, największą i najmniejszą wartość. Otrzymamy 9. Następnie, dodajmy 7 + 1, drugą największą i drugą najmniejszą wartość. Otrzymamy ponownie 9. Co z 6 + 3? Również 9. W końcu, 5 + 4. Ponownie 9!
(8+1)+(7+2)+(6+3)+(5+4)=9+9+9+9=49=36 . \begin{aligned} (8 + 1) + (7 + 2) + (6 + 3) + (5 + 4) &= 9 + 9 + 9 + 9 \\ &= 4 \cdot 9 \\ &= 36 \ . \end{aligned}
Otrzymaliśmy cztery pary liczb, każda z tych par dawała w sumie 9. Więc oto sposób na policzenie sumy dowolnego ciągu kolejnych liczb całkowitych:
  1. Dodaj najmniejszą i największą liczbę.
  2. Pomnóż przez liczbę par.
Co z nieparzystymi ciągami liczb, których nie da się podzielić w pary? Nasz sposób dalej działa! Wystarczy policzyć środkową liczbę jako połowę pary. Na przykład, policzmy sumę 1 + 2 + 3 + 4 + 5. Mamy dwie pary (1 + 5 i 2 + 4, obydwie sumujące siędo 6) i jedną "półparę" (3, czyli połowa z 6), co daje łącznie 2,5 pary. Mnożąc 2.56=15 2.5 \cdot 6 = 15 otrzymujemy poprawną odpowiedź.
Co jeśli rozważymy ciąg od 1 do n n ? Nazywamy go ciągiem arytmetycznym. Suma najmniejszej i największej liczby, to n+1 n + 1 . Ponieważ mamy razem n n liczb, otrzymamy n/2 n/2 par (bez względu na to czy n n jest parzyste czy nieparzyste). Oznacza to, że suma liczb od 1 do n n wynosi (n+1)(n/2) (n + 1)(n/2) , czyli n2/2+n/2 n^2/2 + n/2 . Wypróbuj ten wzór dla n=5 n = 5 i n=8 n = 8 .

Analiza asymptotycznego czasu wykonania sortowania przez wybieranie

Całkowity czas wykonywania sortowania przez wybieranie składa się z trzech części:
  1. Czas wykonania wszystkich wywołań indexOfMinimum.
  2. Czas wykonania wszystkich wywołać swap.
  3. Czas wykonania pozostałej części pętli w funkcji selectionSort.
Części 2 i 3 są proste. Wiemy że funkcja swap będzie wywołana n n razy i każde wywołanie wykonuje się w czasie stałym. Używając notacji asymptotycznej, czas wykonania wszystkich wywołać swap to Θ(n) \Theta(n) . Pozostała część pętli w selectionSort to jedynie sprawdzenie i zwiększenie indeksu pętli oraz wywołanie indexOfMinimum i swap, co również wykona się w czasie stałym dla każdej z n n iteracji, dając kolejne Θ(n) \Theta(n) .
Jeśli chodzi o część 1 - czas wykonania wszystkich wywołań indexOfMinimum - najtrudniejsze już jest za nami. Każde pojedyncze wykonanie treści pętli w indexOfMinimum wykona się w czasie stałym. Liczba iteracji tej pętli to n n w pierwszym wywołaniu, następnie n1 n-1 , potem n2 n-2 itd. Widzieliśmy już tę sumę, 1+2++(n1)+n 1 + 2 + \cdots + (n-1) + n to ciąg arytmetyczny i jego wartość wynosi (n+1)(n/2) (n+1)(n/2) , lub n2/2+n/2 n^2/2 + n/2 . Tak więc czas wykonania wszystkich wywołań indexOfMinimum to czynnik stały pomnożony przez n2/2+n/2 n^2/2 + n/2 . W notacji asymptotycznej nie musimy się przejmować czynnikiem stałym, dzieleniem przez 2 ani składnikiem niższego stopnia. Pozostaje jedynie n2 n ^ 2 , które jest też wartością czasu wykonania wszystkich wywołań indexOfMinimum: Θ(n2) \Theta(n^2) .
Dodając czasy wykonania wszystkich trzech części otrzymujemy Θ(n2) \Theta(n^2) dla wywołań indexOfMinimum, Θ(n) \Theta(n) dla wywołań swap i Θ(n) \Theta(n) dla pozostałej części pętli w selectionSort. Składnik Θ(n2) \Theta(n^2) jest najbardziej znaczący, co oznacza że czas wykonania sortowania przez wybór to Θ(n2) \Theta(n^2) .
Zwróć uwagę, że żaden przypadek nie będzie szczególnie dobry lub zły dla sortowania przez wybór. Pętla w indexOfMinimum zawsze wykona się w n2/2+n/2 n^2/2 + n/2 iteracjach, bez względu na tablicę na wejściu. Oznacza to że możemy powiedzieć że sortowanie przez wybór wykona się w czasie Θ(n2) \Theta(n^2) we wszystkich przypadkach.
Rozważmy jak czas asymptotyczny Θ(n2) \Theta(n^2) wpłynie na faktyczny czas wykonania w różnych przypadkach. Powiedzmy że sortowanie przez wybór wymaga n2/106 n^2/10^6 sekund do posortowania n n wartości. Zacznijmy od niewielkich wartości n n , np. n=100 n = 100 . Czas wykonania sortowania przez wybór wyniesie 1002/106=1/100 100^2/10^6 = 1/100 sekund. Wydaje się to być niezłym wynikiem. Ale co jeśli zwiększymy n n do n=1000 n = 1000 ? Wtedy sortowanie zajmie 10002/106=1 1000^2/10^6 = 1 sekundę. Rozmiar tablicy urósł dziesięciokrotnie, ale czas wykonania wzrósł 100 razy. Co jeśli n=1 000 000 n = 1~000~000 ? Wtedy sortowanie przez wybór zajmie 1 000 0002/106=1 000 000 1~000~000^2/10^6 = 1~000~000 sekund, czyli trochę ponad 11,5 11{,}5 dnia. Zwiększenie rozmiaru tablicy 1000-krotnie zwiększyło czas wykonania milion razy!

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.
Ładowanie