If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

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, procedura ta zostanie powtórzona 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 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 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

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, point, 5, dot, 6, equals, 15 otrzymujemy poprawną odpowiedź.
Co jeśli rozważymy ciąg od 1 do n? Nazywamy go ciągiem arytmetycznym. Suma najmniejszej i największej liczby, to n, plus, 1. Ponieważ mamy razem n liczb, otrzymamy n, slash, 2 par (bez względu na to czy n jest parzyste czy nieparzyste). Oznacza to, że suma liczb od 1 do n wynosi left parenthesis, n, plus, 1, right parenthesis, left parenthesis, n, slash, 2, right parenthesis, czyli n, squared, slash, 2, plus, n, slash, 2. Wypróbuj ten wzór dla n, equals, 5 i n, equals, 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 razy i każde wywołanie wykonuje się w czasie stałym. Używając notacji asymptotycznej, czas wykonania wszystkich wywołać swap to \Theta, left parenthesis, n, right parenthesis. 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 iteracji, dając kolejne \Theta, left parenthesis, n, right parenthesis.
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 w pierwszym wywołaniu, następnie n, minus, 1, potem n, minus, 2 itd. Widzieliśmy już tę sumę, 1, plus, 2, plus, \@cdots, plus, left parenthesis, n, minus, 1, right parenthesis, plus, n to ciąg arytmetyczny i jego wartość wynosi left parenthesis, n, plus, 1, right parenthesis, left parenthesis, n, slash, 2, right parenthesis, lub n, squared, slash, 2, plus, n, slash, 2. Tak więc czas wykonania wszystkich wywołań indexOfMinimum to czynnik stały pomnożony przez n, squared, slash, 2, plus, n, slash, 2. W notacji asymptotycznej nie musimy się przejmować czynnikiem stałym, dzieleniem przez 2 ani składnikiem niższego stopnia. Pozostaje jedynie n, squared, które jest też wartością czasu wykonania wszystkich wywołań indexOfMinimum: \Theta, left parenthesis, n, squared, right parenthesis.
Dodając czasy wykonania wszystkich trzech części otrzymujemy \Theta, left parenthesis, n, squared, right parenthesis dla wywołań indexOfMinimum, \Theta, left parenthesis, n, right parenthesis dla wywołań swap i \Theta, left parenthesis, n, right parenthesis dla pozostałej części pętli w selectionSort. Składnik \Theta, left parenthesis, n, squared, right parenthesis jest najbardziej znaczący, co oznacza że czas wykonania sortowania przez wybór to \Theta, left parenthesis, n, squared, right parenthesis.
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 n, squared, slash, 2, plus, n, slash, 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 \Theta, left parenthesis, n, squared, right parenthesis we wszystkich przypadkach.
Rozważmy jak czas asymptotyczny \Theta, left parenthesis, n, squared, right parenthesis wpłynie na faktyczny czas wykonania w różnych przypadkach. Powiedzmy że sortowanie przez wybór wymaga n, squared, slash, 10, start superscript, 6, end superscript sekund do posortowania n wartości. Zacznijmy od niewielkich wartości n, np. n, equals, 100. Czas wykonania sortowania przez wybór wyniesie 100, squared, slash, 10, start superscript, 6, end superscript, equals, 1, slash, 100 sekund. Wydaje się to być niezłym wynikiem. Ale co jeśli zwiększymy n do n, equals, 1000? Wtedy sortowanie zajmie 1000, squared, slash, 10, start superscript, 6, end superscript, equals, 1 sekundę. Rozmiar tablicy urósł dziesięciokrotnie, ale czas wykonania wzrósł 100 razy. Co jeśli n, equals, 1, space, 000, space, 000? Wtedy sortowanie przez wybór zajmie 1, space, 000, space, 000, squared, slash, 10, start superscript, 6, end superscript, equals, 1, space, 000, space, 000 sekund, czyli trochę ponad 11, comma, 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.