[ Pobierz całość w formacie PDF ]
Wykonuje więc ona n cykli, gdzie n jest równe uMaxIndex - uMinIndex + 1. Jej
zÅ‚ożoność jest liniowa - ˜(n).
Reszta algorytmu nie przekracza tej klasy. Wypełnienie wartościami dwóch pomocniczych
tablic aLewa i aPrawa także wymaga liczby instrukcji proporcjonalnej do n. Jeśli zaś
założymy, że operacje alokacji pamięci i jej zwalniania są wykonywane w czasie stałym
(co jest rozsądne dla niemal wszystkich komputerów), to ze strony złożoności algorytmu
łączenia podtablic nie spotkają nas już żadne niespodzianki.
Ostatecznie wiÄ™c jest on rzÄ™du ˜(n).
Złożoność teoretyczna
Wiemy teraz, jak efektywne jest zrealizowanie pojedynczego wywołania rekurencyjnego
w sortowaniu mergesort. Nie wiemy jednak, ile takich wywołań rzeczywiście występuje i
jak bardzo wielkość ta zależy od n - rozmiaru sortowanej tablicy. Ażeby to oszacować,
musimy przyjrzeć się zastosowanej rekursji i w ten sposób wyznaczyć funkcję złożoności
dla całego algorytmu.
Zobaczmy więc, jak mergesort wywołuje sam siebie. Z opisu podanego w poprzednim
paragrafie powinieneś jeszcze pamiętać, że istotą jest tu podział tablicy na dwie połowy. I
tak się faktycznie dzieje: wyznaczany jest po prostu graniczny indeks połówkowy ,
wedle którego dokonywany jest podział (przechowuje go zmienna uPunktPodziału).
A gdy dokonało się dzielenie, czas na zwycięstwo. Obie podtablice są więc sortowane
poprzez ten sam algorytm mergesort - z tą różnicą, że jest on wywoływany dla każdej z
nich osobno. Rekurencyjne wywołania procedury operują już zatem na tablicach o
rozmiarze nie n, lecz mniej więcej8 n/2.
8
%7ładen element nie może rzecz jasna zostać zgubiony. W rzeczywistości pierwsza rekurencja zajmuje się więc
podtablicą o rozmiarze (połowa liczby elementów zaokrąglona w doł), zaś druga - o rozmiarze
¢# ¥# ¡# ¤#
£#n 2¦# ¢#n 2¥#
(połowa liczby element zaokrąglona w górę). Dla analizy algorytmu jest to jednak szczegół techniczny, bo skoro
wszystkie elementy i tak są brane pod uwagę, możemy swobodnie założyć, że obie połówki mają po prostu n/2
elementów.
Wartość T(n) złożoności praktycznej jest więc budowana przez wartości T(n/2),
reprezentujące rekurencję dla tablic połówkowych, oraz złożoność procesu łączenia -
˜(n). W sumie wynosi ona zatem:
T n = 2T n 2 + ˜ n
( ) ( ) ( )
Należy jeszcze uwzględnić przypadek elementarny - jest nim tablica składająca się tylko z
jednego elementu. Naturalnie jest on posortowana, toteż do algorytmu należy jedynie
stwierdzenie tego faktu. Jest to wykonywane w czasie staÅ‚ym - ˜(1).
Finalna postać zależności T(n) jest więc następująca:
§# ˜ 1dla n d"1
( )
ª#
T n =
( )
¨#2T n 2 + ˜ n dla n >1
( ) ( )
ª#
©#
Teraz pozostaje nam tylko jej rozwiÄ…zanie, czyli wyznaczenie T(n) jako funkcji
nierekurencyjnej. W następnym paragrafie zajmiemy się tym głównym punktem
programu.
Jeżeli posługiwanie się notacjami asymptotycznymi w równaniach sprawia ci jeszcze
kÅ‚opot, to możesz przyjąć, że pod ˜(1) kryje siÄ™ c, zaÅ› pod ˜(n) - dn, gdzie c i d sÄ…
dowolnymi stałymi. Ja jednak będę stosował ten zapis jako wygodniejszy i podkreślający
fakt, że zależy nam wyznaczeniu złożoności asymptotycznej bez wdawania się w zbędne
szczegóły. WÅ‚aÅ›ciwie wiÄ™c notacjÄ™ ˜ należaÅ‚oby tu traktować jako pewne uproszczenie!
RozwiÄ…zanie rekurencji
Już pierwszy rzut oka na równanie
T n = 2T n 2 + ˜ n
( ) ( ) ( )
utwierdza nas w przekonaniu, że różni się ono trochę od tych, którymi zajmowaliśmy się
dotąd. Pomijając występowanie więcej niż jednego składnika rekurencyjnego (z czym
nauczyliśmy sobie jakoś radzić), zamieszanie wprowadza z pewnością n/2 jako jego
argument.
Dzielenie rozmiaru danych na połowę lub dowolną inną liczbę części jest jednak (jak
nawet sama nazwa wskazuje) nieodłącznym elementem techniki dziel i zwyciężaj . Gdy
więc poznamy sposób na rozwikłanie powyższej funkcji jest wielce prawdopodobne, że
analogiczne metody dadzą się zastosować dla przynajmniej większości algorytmów
stosując ww. technikę. W tym paragrafie pokażę kilka takich sposobów.
Na początek jednakowoż wypadałoby podjąć wyzwanie i oszacować powyższą funkcję
T(n) dla sortowania przez scalanie. Mimo pozornej trudności zadanie to może okazać się
całkiem łatwe&
Jeszcze raz drzewko
Oczywiście metoda rozpisywania na pewno nie zda tu egzaminu, gdyż czynnik 2 przy
T(n/2) znakomicie uniemożliwia zredukowanie wszystkich składników poza T(n).
Poradziliśmy już sobie jednak w takiej sytuacji: pomocą okazało się zilustrowanie
rekurencji za pomocÄ… poglÄ…dowego drzewka.
Spróbujmy więc wykorzystać tę metodę także i tutaj. Przypomnijmy, że drzewko jest
skonstruowane wedle trzech reguł:
każdy jego węzeł odpowiada nierekurencyjnej część równania - tej, którą znamy
bezpośrednio, niezawierającej dalszych wywołań T(...)
krawędz (gałąz) drzewa wychodząca z danego węzła reprezentuje wywołania
rekurencyjne
liście drzewa odpowiadają przypadkom elementarnym, kończącym rekurencję
Jak to wyglÄ…da u nas?& SkÅ‚adnikiem nierekurencyjnym w T(n) jest ˜(n) - przypomnijmy,
że jest to synonim dowolnej funkcji liniowej. Pojawi się on więc w korzeniu i
wewnętrznych węzłach drzewa. Z kolei krawędzie są modelem przywołań rekurencyjnych.
Od korzenia odchodzą więc dwie gałęzie T(n/2), na drugim poziomie - T(n/4), potem
T(n/8), itd. Wreszcie, drzewo kończy się na przypadkach elementarnych, gdy n nie
można już podzielić na dwa. W liÅ›ciach znajdzie siÄ™ wiÄ™c ˜(1).
Opierając się na tych spostrzeżeniach możemy zasadzić drzewko:
Schemat 4. Drzewo rekursji dla złożoności teoretycznej sortowania przez scalanie - etap pierwszy
Pod wielokropkami kryją się oczywiście rekurencyjne poddrzewa. Gdy więc nasze
drzewko urośnie nieco bardziej, wyglądać będzie mniej więcej tak:
Schemat 5. Drzewo rekursji dla złożoności teoretycznej sortowania przez scalanie - etap drugi
Jak widzimy, kolejne wywołania są przeprowadzane dla coraz mniejszych wartości n -
połówek, połówek połówek, połówek ćwierci, itd. W wyniku tego podziału dojdziemy w
[ Pobierz całość w formacie PDF ]