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 scalanie

Biorąc pod uwagę, że scalanie potrzebuje Θ(n) czasu na scalenie n elementów, w jaki sposób możemy wywnioskować, że mergeSort działa w czasie rzędu Θ(nlog2n)? 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 Θ(1).
  2. Krok conquer (rządź), w którym rekurencyjnie sortujemy dwie macierze zawierające w przybliżeniu n/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 Θ(n).
Jeśli pomyślimy o krokach "dziel" i "połącz" jednocześnie, czas wykonania Θ(1) dla kroku "dziel" jest bardzo niewielki w porównaniu z czasem wykonania Θ(n) w kroku połączenia. Więc pomyślmy o krokach "dziel" i "połącz" jednocześnie, biorąc pod uwagę czas Θ(n). Aby te rozważanie stały się bardziej konkretne, powiedzmy, że kroki "dziel" i "połącz" zajmują razem cn czasu dla jakiejś stałej c.
Aby nasze rozważania wciąż były dość proste, załóżmy, że jeśli n>1, wtedy n jest zawsze parzyste, więc jeśli myślimy o liczbie n/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 (n/2)-elementowej podtablicy (dla kroku "rządź") oraz cn (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/2 elementów. Każde z tych dwóch rekurencyjnych odwołań zabiera dwukrotność czasu wykonania funkcji mergeSort na (n/4)-elementowej podtablicy (ponieważ musimy podzielić na pół n/2) oraz cn/2 czasu potrzebnego na scalanie. Mamy zatem dwa pod-problemy rozmiaru n/2, a każdy z nich zajmuje cn/2 czasu do scalenia, więc całkowity czas na wykonanie scalania pod-problemów o rozmiarze n/2 wynosi 2cn/2=cn.
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/2 reprezentującą rozmiar podtablic dla dwóch podproblemów o rozmiarze n/2.
Każdy z pod-problemów o rozmiarze n/2 rekurencyjnie sortuje dwie podtablice o rozmiarze (n/2)/2 lub n/4. Mamy tutaj dwa podproblemy o rozmiarze n/2, czyli, inaczej mówiąc, są to cztery podproblemy o rozmiarze n/4. Każdy z tych czterech podproblemów scala łącznie n/4 elementów, czyli czas wykonania scalania dla każdego z tych czterech podproblemów to cn/4. Podsumowując nasze rozważania stwierdzamy że ogólny czas scalania wszystkich podproblemów o rozmiarze n/4 wynosi 4cn/4=cn:
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/8? Będzie wówczas osiem takich podproblemów, a czas scalania dla każdego z nich będzie wynosił cn/8, a z kolei całkowity czas scalania to 8cn/8=cn:
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 cn 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ć Θ(1) czasu, ponieważ za każdym razem sprawdzamy czy p<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 Θ(1) czasu, możemy powiedzieć, że wszystkie przypadki bazowe trwają cn 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 lcn. 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=log2n+1. Na przykład: dla n=8, mamy log2n+1=4, i z pewnością drzewo posiada cztery poziomy: n=8,4,2,1. Całkowity czas wykonania mergeSort wynosi wtedy cn(log2n+1). Używając notacji big-Θ do opisania czasu wykonania algorytmu, można odrzucić czynnik nieznaczący (+1) oraz stały współczynnik (c), aby uzyskać w ten sposób czas Θ(nlog2n), 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?

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