Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 1
Lekcja 4: Sortowanie przez wybieranie- Sortowanie
- Wyzwanie: zamiana wartości zmiennych
- Sortowanie przez wybieranie - pseudokod
- Wyzwanie: znajdź najmniejszy element w podtablicy
- Wyzwanie: realizacja sortowania przez wybieranie
- Analiza sortowania przez wybieranie
- Projekt: wizualizacja sortowania przez wybieranie
© 2023 Khan AcademyWarunki użytkowaniapolitykę prywatnościInformacja o plikach cookie
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.
- W pierwszym wywołaniu
indexOfMinimummusi odwiedzić każdą wartość w tablicy więc treść pętliindexOfMinimumwykona się 8 razy. - W drugim wywołaniu
indexOfMinimum, funkcja musi odwiedzić każdą wartość w podtablicy na pozycjach 1 do 7, więc treść pętli windexOfMinimumwykona się 7 razy. - W trzecim wywołaniu, funkcja odwiedzi wartości w podtablicy na pozycjach 2 do 7, czyli pętla wykona się 6 razy.
- W czwartym wywołaniu zajmie się podtablicą na pozycjach 3 do 7, pętla wykona się 5 razy.
- …
- 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!
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:
- Dodaj najmniejszą i największą liczbę.
- 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:
- Czas wykonania wszystkich wywołań
indexOfMinimum. - Czas wykonania wszystkich wywołać
swap. - 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.
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji