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 2n 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 .
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 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+1. Ponieważ mamy razem n liczb, otrzymamy n/2 par (bez względu na to czy n jest parzyste czy nieparzyste). Oznacza to, że suma liczb od 1 do n wynosi (n+1)(n/2), czyli n2/2+n/2. Wypróbuj ten wzór dla n=5 i 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 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). 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 Θ(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 w pierwszym wywołaniu, następnie n1, potem n2 itd. Widzieliśmy już tę sumę, 1+2++(n1)+n to ciąg arytmetyczny i jego wartość wynosi (n+1)(n/2), lub n2/2+n/2. Tak więc czas wykonania wszystkich wywołań indexOfMinimum to czynnik stały pomnożony przez n2/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, które jest też wartością czasu wykonania wszystkich wywołań indexOfMinimum: Θ(n2).
Dodając czasy wykonania wszystkich trzech części otrzymujemy Θ(n2) dla wywołań indexOfMinimum, Θ(n) dla wywołań swap i Θ(n) dla pozostałej części pętli w selectionSort. Składnik Θ(n2) jest najbardziej znaczący, co oznacza że czas wykonania sortowania przez wybór to Θ(n2).
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 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) we wszystkich przypadkach.
Rozważmy jak czas asymptotyczny Θ(n2) wpłynie na faktyczny czas wykonania w różnych przypadkach. Powiedzmy że sortowanie przez wybór wymaga n2/106 sekund do posortowania n wartości. Zacznijmy od niewielkich wartości n, np. n=100. Czas wykonania sortowania przez wybór wyniesie 1002/106=1/100 sekund. Wydaje się to być niezłym wynikiem. Ale co jeśli zwiększymy n do n=1000? Wtedy sortowanie zajmie 10002/106=1 sekundę. Rozmiar tablicy urósł dziesięciokrotnie, ale czas wykonania wzrósł 100 razy. Co jeśli n=1 000 000? Wtedy sortowanie przez wybór zajmie 1 000 0002/106=1 000 000 sekund, czyli trochę ponad 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.

Chcesz dołączyć do dyskusji?

Na razie brak głosów w dyskusji
Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.