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ść

Informatyka

Kurs: Informatyka > Jednostka 1

Lekcja 8: Sortowanie przez scalanie
Informatyka
Informatyka
Algorytmy
Sortowanie przez scalanie
© 2023 Khan AcademyWarunki użytkowaniapolitykę prywatnościInformacja o plikach cookie

Analiza sortowania przez scalanie

Google Classroom
Biorąc pod uwagę, że scalanie potrzebuje \Theta, left parenthesis, n, right parenthesis czasu na scalenie n elementów, w jaki sposób możemy wywnioskować, że mergeSort działa w czasie rzędu \Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis? Zaczniemy od zastanowienia nad trzema częściami algorytmu divide-and-conquer i w jaki sposób obliczyć czas, potrzebny wszystkim tym trzem częściom z osobna . Załóżmy, że mamy posortować tablicę, zawierającą n elementów.
  1. Krok divide (dziel) wymaga stałego czasu, niezależnego od rozmiaru podtablicy. W tym kroku po prostu obliczamy indeks q elementu leżącego pomiędzy elementami o indeksach p i r. W notacji duże-Θ, stały czas wykonania oznaczamy jako \Theta, left parenthesis, 1, right parenthesis.
  2. Krok conquer (rządź), w którym rekurencyjnie sortujemy dwie macierze zawierające w przybliżeniu n, slash, 2 elementów każda, wymaga pewnego czasu, który uwzględnimi, gdy zajmiemy się podproblemami.
  3. Krok combine (połącz) scala w sumie n elementów w czasie zmieniającym się jak \Theta, left parenthesis, n, right parenthesis.
Jeśli pomyślimy o krokach "dziel" i "połącz" jednocześnie, czas wykonania \Theta, left parenthesis, 1, right parenthesis dla kroku "dziel" jest bardzo niewielki w porównaniu z czasem wykonania \Theta, left parenthesis, n, right parenthesis w kroku połączenia. Więc pomyślmy o krokach "dziel" i "połącz" jednocześnie, biorąc pod uwagę czas \Theta, left parenthesis, n, right parenthesis. Aby te rozważanie stały się bardziej konkretne, powiedzmy, że kroki "dziel" i "połącz" zajmują razem c, n czasu dla jakiejś stałej c.
Aby nasze rozważania wciąż były dość proste, załóżmy, że jeśli n, is greater than, 1, wtedy n jest zawsze parzyste, więc jeśli myślimy o liczbie n, slash, 2, to jest ona zawsze liczbą całkowitą. (Obliczenia dla przypadku, w którym n jest nieparzyste, nie zmieniają wyniku w notacji duże-Θ .) Teraz więc możemy pomyśleć o czasie wykonania funkcji mergeSort na n-elementowej podtablicy, który jest sumą czasów wykonania się funkcji: mergeSort na left parenthesis, n, slash, 2, right parenthesis-elementowej podtablicy (dla kroku "rządź") oraz c, n (dla kroków dzielenia i połączenia— a faktycznie po prostu dla scalania).
Teraz musimy obliczyć czas wykonania dwóch rekurencyjnych odwołań dla n, slash, 2 elementów. Każde z tych dwóch rekurencyjnych odwołań zabiera dwukrotność czasu wykonania funkcji mergeSort na left parenthesis, n, slash, 4, right parenthesis-elementowej podtablicy (ponieważ musimy podzielić na pół n, slash, 2) oraz c, n, slash, 2 czasu potrzebnego na scalanie. Mamy zatem dwa pod-problemy rozmiaru n, slash, 2, a każdy z nich zajmuje c, n, slash, 2 czasu do scalenia, więc całkowity czas na wykonanie scalania pod-problemów o rozmiarze n, slash, 2 wynosi 2, dot, c, n, slash, 2, equals, c, n.
Narysujmy te czasy scalania w postaci "drzewa":
Rysunek z diagramem drzewowym po lewej stronie i czasami scalania po prawej. Drzewo jest opisane jako "Subproblem size", a kolumna po prawej jest opisana jako "Total merging time for all subproblems of this size." Na najwyższym poziomie drzewa znajduje się jeden węzeł n, a odpowiadający mu czas scalania wynosi c razy n. Na drugim poziome drzewa znajdują się dwa węzły, każdy z nich oznaczony jako 1/2 n, a czas scalania wynosi 2 razy c razy 1/2 n, co się równa c times n, jak powyżej.
Informatycy rysują drzewa do góry nogami w porównaniu do drzew, które rosną w rzeczywistości. Drzewo jest grafem nie zwierającym cykli (ścieżek, które zaczynają się i kończą w tym samym miejscu). Według nazewnictwa informatycznego, wierzchołki drzewa nazywane są węzłami. Węzeł korzeń jest na samej górze; w naszym przykładzie korzeń jest oznaczony literą n, czyli rozmiarem tablicy n-elementowej. Poniżej korzenia znajdują się dwa węzły dzieci, każdy oznaczony etykietą n, slash, 2 reprezentującą rozmiar podtablic dla dwóch podproblemów o rozmiarze n, slash, 2.
Każdy z pod-problemów o rozmiarze n, slash, 2 rekurencyjnie sortuje dwie podtablice o rozmiarze left parenthesis, n, slash, 2, right parenthesis, slash, 2 lub n, slash, 4. Mamy tutaj dwa podproblemy o rozmiarze n, slash, 2, czyli, inaczej mówiąc, są to cztery podproblemy o rozmiarze n, slash, 4. Każdy z tych czterech podproblemów scala łącznie n, slash, 4 elementów, czyli czas wykonania scalania dla każdego z tych czterech podproblemów to c, n, slash, 4. Podsumowując nasze rozważania stwierdzamy że ogólny czas scalania wszystkich podproblemów o rozmiarze n, slash, 4 wynosi 4, dot, c, n, slash, 4, equals, c, n:
Rysunek z diagramem drzewkowym po lewej stronie i czasami scalania po prawej. Drzewo jest opisane jako "Subproblem size", a kolumna po prawej jest opisana jako "Total merging time for all subproblems of this size." Na najwyższym poziomie drzewa znajduje się jeden węzeł n, a odpowiadający mu czas scalania wynosi c razy n. Na drugim poziome drzewa znajdują się dwa węzły, każdy z nich oznaczony jako 1/2 n, a czas scalania wynosi 2 razy c razy 1/2 n, co się równa c times n, jak powyżej.
Co stałoby się, gdyby podproblemy były rozmiaru n, slash, 8? Będzie wówczas osiem takich podproblemów, a czas scalania dla każdego z nich będzie wynosił c, n, slash, 8, a z kolei całkowity czas scalania to 8, dot, c, n, slash, 8, equals, c, n:
Rysunek z diagramem drzewkowym po lewej stronie i czasami scalania po prawej. Drzewo jest opisane jako "Subproblem size", a kolumna po prawej jest opisana jako "Total merging time for all subproblems of this size." Na najwyższym poziomie drzewa znajduje się jeden węzeł n, a odpowiadający mu czas scalania wynosi c razy n. Na drugim poziome drzewa znajdują się dwa węzły, każdy z nich oznaczony jako 1/2 n, a czas scalania wynosi 2 razy c razy 1/2 n, co się równa c times n, jak powyżej. Na trzecim poziomie znajdują się cztery węzły, każdy z nich oznaczony jako 1/4 n, a czas scalania wynosi 4 razy c razy 1/4 n, czyli c razy n, jak powyżej. Na czwartym poziomie znajduje się osiem węzłów, każdy z nich oznaczony jako 1/8 n, a czas scalania wynosi 8 razy c razy 1/8 n, czyli c razy n, jak powyżej.
Za każdym razem gdy zmniejszamy podproblemy, ich liczba podwaja się na każdym "poziomie" rekurencji, ale czas scalania jest połowę krótszy. To podwajanie i zmniejszanie redukują się wzajemnie, więc ogólny czas scalania wynosi c, n na każdym poziomie rekurencji. W końcu dochodzimy do podproblemów o rozmiarze 1: do przypadku bazowego. Aby posortować podtablice o rozmiarze 1, musimy mieć \Theta, left parenthesis, 1, right parenthesis czasu, ponieważ za każdym razem sprawdzamy czy p, is less than, r, a to sprawdzenie trwa jakiś czas. Jak wiele jest podtablic o rozmiarze 1? Skoro rozpoczęliśmy od n elementów, musi być dokładnie n takich podtablic. Skoro każdy bazowy przypadek zajmuje \Theta, left parenthesis, 1, right parenthesis czasu, możemy powiedzieć, że wszystkie przypadki bazowe trwają c, n czasu:
Rysunek z diagramem drzewkowym po lewej stronie i czasami scalania po prawej. Drzewo jest opisane jako "Subproblem size", a kolumna po prawej jest opisana jako "Total merging time for all subproblems of this size." Na najwyższym poziomie drzewa znajduje się jeden węzeł n, a odpowiadający mu czas scalania wynosi c razy n. Na drugim poziome drzewa znajdują się dwa węzły, każdy z nich oznaczony jako 1/2 n, a czas scalania wynosi 2 razy c razy 1/2 n, co się równa c times n, jak powyżej. Na trzecim poziomie znajdują się cztery węzły, każdy z nich oznaczony jako 1/4 n, a czas scalania wynosi 4 razy c razy 1/4 n, czyli c razy n, jak powyżej. Na czwartym poziomie znajduje się osiem węzłów, każdy z nich oznaczony jako 1/8 n, a czas scalania wynosi 8 razy c razy 1/8 n, czyli c razy n, jak powyżej. Wielokropek poniżej sugeruje, że drzewko rozwija się dalej w ten sam sposób. Na ostatnim poziomie mamy n węzłów po 1, a czas scalania wynosi n razy c, czyli tyle samo, co c razy n.
Teraz już wiemy jak długo trwa scalanie dla każdego rozmiaru podproblemu. Całkowity czas wykonania funkcji mergeSort jest sumą wszystkich czasów scalania na każdym poziomie. Jeśli mamy l poziomów w drzewie, całkowity czas scalania wynosi l, dot, c, n. Czym zatem jest to l? Zaczynamy od podproblemów o rozmiarze n i powtarzamy dzielenie podproblemów na pół aż osiągniemy podproblemy o rozmiarze 1. Widzieliśmy już tą zależność, gdy analizowaliśmy wyszukiwanie binarne i wynosiła ona l, equals, log, start base, 2, end base, n, plus, 1. Na przykład: dla n, equals, 8, mamy log, start base, 2, end base, n, plus, 1, equals, 4, i z pewnością drzewo posiada cztery poziomy: n, equals, 8, comma, 4, comma, 2, comma, 1. Całkowity czas wykonania mergeSort wynosi wtedy c, n, left parenthesis, log, start base, 2, end base, n, plus, 1, right parenthesis. Używając notacji big-Θ do opisania czasu wykonania algorytmu, można odrzucić czynnik nieznaczący (plus, 1) oraz stały współczynnik (c), aby uzyskać w ten sposób czas \Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis, jak przewidywaliśmy.
Jeszcze jedna rzecz dotycząca sortowania przez scalanie jest warta uwagi. Podczas scalania wykonywana jest kopia całej tablicy, która jest sortowana: jedna połowa znajduje się w lowHalf a druga w highHalf. Ponieważ kopiowana jest więcej niż stała liczba elementów w jednym czasie, mówimy, że sortowanie przez scalanie nie działa w miejscu. Dla kontrastu: zarówno sortowanie przez wybór i przez wstawianie wykonywane są w miejscu, nigdy nie robią kopii większej niż stała liczba elementów tablicy w jednym czasie. Informatycy lubią wiedzieć czy algorytm działa w miejscu, ponieważ w niektórych systemach miejsce jest bardzo ważnym parametrem i dlatego preferowane są wówczas algorytmy działające w miejscu.
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?

Zaloguj się
Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.