BAL - ćwiczenia nr 6

14 grudnia 2011

Złożoność algorytmów

Algorytm Konwersji binarnej

Rozmiar zadania N - wartość liczby konwertowanej.
Funkcja kosztu T (N ) - liczba cyfr w zapisie binarnym (zer i jedynek), czyli tyle
ile wynosi liczba wykonań iteracji.

Dla N będącego potęgą liczby 2 (N = 2

i

) liczba cyfr w zapisie binarnym

T (N ) wynosi i + 1, np.:

i = 1 : 2

(10)

= 2

1
(10)

= 10

(2)

,

i = 3 : 8

(10)

= 2

3
(10)

= 1000

(2)

.

Wykładniki i dwójki obliczamy logarytmując wartości N = 2

i

. W przypadku

N nie będących potęgami dwójki logarytm należy “obciąć” do najbliższej liczby
całkowitej. Otrzymujemy zatem:

T (N ) = [log

2

N ] + 1 ,

(1)

gdzie [ ] jest operacją “wyciągania” części całkowitej.
Obliczamy rząd złożoności asymptotycznej:

T (N )

= O(log

2

N + 1)

= O(log N ) .

(2)

Podstawa logarytmu 2 “ucieka” z końcowego wyrażenia na złożoność asymp-
totyczną, z uwagi na możliwość skorzystania ze wzoru na zmianę podstawy
logarytmu:

log

2

N

=

1

log

p

2

· log

p

N

= C · log

p

N

= O(log

p

N ) ,

a więc podstawa p logarytmu może być dowolna, byle większa od 1.

1

Algorytm przeszukiwania “liniowego”

Rozmiar zadania N - liczba elementów wektora (tablicy jednowymiarowej).
Funkcja kosztu T (N ) - liczba porównań szukanego elementu z elementami wek-
tora.

T (N ) = N ,

T (N ) = O(N ) .

(3)

Tak więc złożoność jest liniowa, co wyjaśnia nazwę algorytmu.

Algorytm wyszukiwanie elementu o maksymalnej wartości

Rozmiar zadania N - liczba elementów wektora (długość wektora).
Funkcja kosztu T (N ) - liczba porównań aktualnego “kandydata” na element
maksymalny z pozostałymi elementami wektora.

T (N ) = N − 1 ,

T (N ) = O(N ) .

(4)

Złożoność jest liniowa.

Analogicznie będzie w przypadku, gdy za operację

dominującą przyjmiemy operację zmiany wartości lidera; w tej sytuacji za-
kładamy scenariusz pesymistyczny (najgorszy z możliwych).

Algorytm sortowania przez selekcję

Rozmiar zadania N - liczba elementów wektora do posortowania.

T (N ) - np. liczba porównań:

T (N )

= (N − 1) + (N − 2) + ... + 2 + 1

=

N −1

X

i=1

i

= (N − 1)

(N − 1) + 1

2

(5)

=

(N − 1) N

2

=

1

2

N

2

−

1

2

N .

Tak więc złożoność asymptotyczna wynosi:

T (N )

= O

 1

2

· N

2

−

1

2

· N



2

= O C

1

N

2

+ C

2

N

(6)

= O N

2

.

Otrzymaliśmy złożoność kwadratową.

Analogiczną analizę przeprowadzamy dla sortowania bąbelkowego (algo-

rytm 09). Tym razem za operację dominującą przyjmujemy zamianę wartości
sąsiednich elementów, otrzymując ten sam wynik co (6).

Algorytm sortowania drzewiastego na kopcu

Rozmiar zadania N - liczba elementów wektora do posortowania.

Ponieważ algorytm rozbiliśmy na oddzielne procedury, (budowa kopca i jego

r ozbiór) funkcję kosztu obliczymy jako sumę kosztów tych procedur:

T (N ) = T

b

(N ) + T

r

(N ) .

(7)

T

b

(N ) będzie zatem liczbą operacji potrzebnych do zbudowania kopca binarnego

z N elementów wektora, zaś T

r

(N ) liczbą operacji potrzebnych do rozebrania

tegoż kopca.

Za operację dominującą przyjmiemy zamianę wartości węzła drzewa z jego

rodzicem. W przypadku zupełnego drzewa binarnego liczba takich zamian, przy
przechodzeniu z pozycji liścia do korzenia, jest o 1 mniejsza niż wysokość drzewa
(liczba poziomów drzewa). Jednocześnie wysokość drzewa pełnego (o maksy-
malnej możliwej dla tej wysokości liczbie węzłów N ) wynosi log

2

(N + 1)(np.

dla liczby węzłów N = 3: h = log

2

(3 + 1) = log

2

4 = log

2

2

2

= 2). Zatem

liczba operacji dominuących dla elementu “dokładanego” do kopca jako i -ty
węzeł wynosi log

2

(i + 1) − 1.

Przy powtarzaniu tej procedury od i = 1 do N otrzymujemy zatem:

T

b

(N )

=

N

X

i=1

(log

2

(i + 1) − 1)

=

N +1

X

i=2

log

2

i

!

− N .

(8)

Tym razem nie możemy tak łatwo jak w przypadku (5) poradzić sobie z wys-
tępującą w (8) sumą ciągu, gdyż nie jest to ciąg arytmetyczny. Musimy przyjąć
“na wiarę”, że:

P

N +1
i=2

log

2

i

= 1 + ... + log

2

(N + 1)

= (N − 1) · (C · log

2

N )

(9)

gdzie C · log

2

N jest średnią wartością (N − 1) elementów ciągu, zaś C jest

pewną stałą liczbą większą od 1.

Zbierając razem informacje z (8) i (9) otrzymujemy:

3

T

z

(N ) = C · (N − 1) log

2

N .

(10)

Analogicznie postępujamy z procedurą rozbioru drzewa; rozumowanie jest dokład-
nie to samo, zliczamy tym razem zamiany wartości par elementów typu rodzic-
potomek, poczynając od korzenia, aż do ostatniego poziomu:

T

r

(N ) = C · (N − 1) log

2

N .

(11)

Ostatecznie z (8), (9), (10) oraz (11) otrzymujemy:

T (N )

= 2C · (N − 1) log

2

N

(12)

= O (N log N ) .

(13)

Otrzymaliśmy zatem złożoność rzędu O (N log N ), a zatem dużo lepszą niż w
przypadku sortowania przez wstawianie czy też bąbelkowego.

4