Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 1
Lekcja 8: Sortowanie przez scalanieAnaliza sortowania przez scalanie
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.- 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.
- 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.
- 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":
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:
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:
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:
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?
- czy ktoś mi wyjaśni do czego mi się to przyda(1 głos)
- To już wszystko zalezy od Ciebie. Przyda Ci się to przede wszystkim do własnego rozwoju, aby później w pracy rozwiązywać bardziej złozone problemy.(1 głos)