Badanie złożoności algorytmów cz II 1

BADANIE ZŁOŻONOŚCI ALGORYTMÓW CZĘSC II

Rekurencja - a sprawność algorytmu:

Algorytmy rekurencyjne bywają zwykle szybsze od analogicznych algorytmów iteracyjnych w sensie złożoności obliczeniowej, choć nie chodzi tu o rząd wielkości a raczej o czynnik skalujący.

Posłużmy się tu przykładem:

Rozważmy algorytm znajdujący maksymalny i minimalny element spośród listy L. Taki algorytm ma złożoność O (W) i żadnymi sztuczkami nie da się tego poprawić.

Prosty algorytm iteracyiny polega na przeglądnięciu wszystkich elementów i porównaniu każdego z nich dwa razy: raz z elementem maksymalnym a raz z minimalnym.

Może on mieć postać:

MAK = MIN = L (1)

dla I = 2, N wykonaj

jeśli L (I) > MAK podstaw MAK = L (I)

jeśli L (I) < MIN podstaw MIN = L (I)

Czas wykonania takiego algorytmu może być szacowany przez funkcję T = C (N) = 2N.

Rozważmy teraz rekurencyjny odpowiednik tego algorytmu:

Procedura "minmax" dla L:

jeśli Ljednoelem. zwróć MIN = MAK = wartość elementu jeśli L dwuelem.

zwróć wartość mniejszego elementu jako MIN zwróć wartość większego elementu jako MAK w przeciwnym razie

podziel listę na 2: L1 i L2 o N / 2 elementów wywołaj "minmaK" dla L1 i oznacz wyniki MIN1, MAK1 wywołaj "minmaK" dla L2 i oznacz wyniki MIN2, MAX2 zwróć MIN jako mniejszą z wartości MIN1 i MIN2 zwróć MAK jako większą z wartości MAK1 i MAX2

Co możemy powiedzieć o funkcji C (N) = aN + b (bo zakładamy liniową):

a.    dla 2 elementów listy mamy porównanie C (2) = 1

b.    dla N > 2 dzieli się listę na dwie części i rozwiązuje zadanie dla N i 2, a potem jeszcze dodatkowo 2 porównania

zatem:

złożoność (N) = złożoność (N / 2) x 2 + 2 czyli C (N) = 2C (N/2) +2

stąd aN + b = 2a N/2 +2b +2 =» b = —2 z C (2) = 1 =* a2 + b =1 2a — 2 = 1 a = 3/2

ostatecznie C (N) = 3/2 N — 2

Zatem nadal mamy złożoność klasy O (N), ale mniejszą niż procedury iteracyjnej. Zysk nie jest zbyt duży ale widoczny.

(Dla N = 1 żadnych porównań C (1) = -'A i przypisujmy jej C (1) = O)

Okazuje się, że także w prostym algorytmie iteracyjnym można osiągnąć złożoność 3N/2 w sposób następujący:

•    powiążmy N elementów w pary

•    porównajmy w każdej parze elementy i zaznaczmy większy z nich =» N 12 par

•    przebiegnijmy N i 2 większych elementów śledząc bieżące maksimum =» N i 2 par porównań

•    przebiegnijmy N / 2 mniejszych elementów śledząc bieżące minimum =*• N / 2 par porównań

Czyli kosztowało nas to 3N / 2 porównań, stąd złożoność O (3N /2)