a < b
tmp �! a
a �! b
b �! tmp
a < c
tmp �! a
a �! c
c �! tmp
a < b + c
1310 = 8 + 4 + 1
= 1 � 23 + 1 � 22 + 0 � 21 + 1 � 20
= 11012 .
13 : 2 = 6
6 : 2 = 3
3 : 2 = 1
1 : 2 = 0
 a > 0
a > 0
a �! [a/2]
13 mod 2 = 1 [ ]
[6.5] = 6
a = 0
a e" 0
a �! [a/2]
a > 0
a = 0
 a > 0
i �! 1
i < a
i �! i � 2
i �! i/2
a > 0
[a/i]
a �!
i �! i/2
0.5 = 1 .
a = 0
 a > 0
i �! [log2 a]
k �! 2i
a > 0
[a/k]
a �!
k �! [k/2]
[log2 a] + 1
a > 0
i �! 1
T ABi �!
a �! [a/2]
i �! i + 1
a > 0
i �! i - 1
T ABi
i > 1
a = 0
T AB(N)
i �! 1
T ABi = x i d" N

i �! i + 1
i d" N
 T AB(N)
max �! T AB1
i �! 2
i d" N
max < T ABi
max �! T ABi
i �! i + 1
 T (N)
L �! 1
P �! N
L < P
TL = 0
L �! L + 1
TP = 1
P �! P - 1
TL < TP
(TL, TP )
L �! L + 1
P �! P - 1
T (N)
T (N)
i = 1 i = N - 1
max �! i
j = i + 1 N
Tj > Tmax
max �! j
(Ti, Tmax)
T (N)
Ti, Ti+1, . . . , TN
Ti
 T (N)
i = 1 N - 1
j = 1 N - i
Tj > Tj+1
(Tj, Tj+1)
T (N)
T (N)
i = 2 N
pom �! Ti
j �! i
j > 1 Tj-1 > pom
Tj �! Tj-1
j �! j - 1
Tj �! pom
T (N)
 T AB(N)
L �! 1
P �! N
L d" P
S �! [(L + P )/2]
T ABS = x
T ABS > x
P �! S - 1
L �! S + 1
T ABS = x
 T AB(N)
T AB(N), x, lewy
lewy > N
T ABlewy = x
T AB(N), x, lewy + 1
N = 0 N = 1
Mod(m, n) = 0
Mod(m, n)
 (N, a, b)
N = 1
 T (N)
T (N)
m = N 2
Tm, T1
T (m - 1)
T (N)
 T (N)
T (N)
m = 2 N
rodz �! [m/2]
rodz > 0 Trodz < Tm
Trodz Tm
m �! [m/2]
rodz �! [m/2]
T (N)
T (N)
T (N)
i �! 2
i d" N
i < N Ti < Ti+1
i �! i + 1
rodz �! [i/2]
Trodz e" Ti
Ti Trodz
i �! i � 2
T (N)
BAL - ćwiczenia nr 6
14 grudnia 2010
Złożoność algorytmów
Algorytm 02 Konwersja binarna
Rozmiar zadania N - wartość liczby konwertowanej a.
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 = 2i) liczba cyfr w zapisie binarnym
T (N) wynosi i + 1, np.:
i = 1 : 2(10) = 21 = 10(2) ,
(10)
i = 3 : 8(10) = 23 = 1000(2) .
(10)
Wykładniki i dwójki obliczamy logarytmując wartości N = 2i. 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) = [log2 N] + 1 , (1)
gdzie [ ] jest operacją  wyciągania części całkowitej.
Obliczamy rząd złożoności asymptotycznej:
T (N) = O(log2 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:
1
log2 N = � logp N
logp 2
= C � logp N
= O(logp N) ,
a więc podstawa p logarytmu może być dowolna, byle większa od 1.
1
Algorytm 05 Przeszukiwanie wektorów nieuporządkowanych
(przeszukiwanie  liniowe )
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 06 Wyszukiwanie elementu maksymalnego w wek-
torze nieuporządkowanym
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 08 Sortowanie przez wstawianie
Rozmiar zadania N - liczba elementów wektora do posortowania.
T (N) - np. liczba  przesunięć elementów wektora T z pozycji j na j + 1:
T (N) = 1 + 2 + ... + (N - 1)
N-1
= i
i=1
1 + (N - 1)
= (N - 1) (5)
2
(N - 1) N
=
2
1 1
= N2 - N .
2 2
Tak więc złożoność asymptotyczna wynosi:
1 1
T (N) = O � N2 - � N
2 2
= O C1N2 + C2N (6)
= O N2 .
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 14 Sortowanie drzewiaste na kopcu
Rozmiar zadania N - liczba elementów wektora do posortowania.
Ponieważ algorytm rozbiliśmy na oddzielne procedury, (budowa kopca i jego
rozbiór) funkcję kosztu obliczymy jako sumę kosztów tych procedur:
T (N) = Tb(N) + Tr(N) . (7)
Tb(N) będzie zatem liczbą operacji potrzebnych do zbudowania kopca binarnego
z N elementów wektora, zaś Tr(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 log2 (N + 1)(np.
dla liczby węzłów N = 3: h = log2(3 + 1) = log2 4 = log2 22 = 2). Zatem
liczba operacji dominuących dla elementu  dokładanego do kopca jako i-ty
węzeł wynosi log2(i + 1) - 1.
Przy powtarzaniu tej procedury od i = 1 do N otrzymujemy zatem:
N
Tb(N) = (log2(i + 1) - 1)
i=1
N+1
= log2 i - N . (8)
i=2
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:
N+1
log2 i = 1 + ... + log2 (N + 1)
i=2
= (N - 1) � (C � log2 N) (9)
gdzie C � log2 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:
Tz(N) = C � (N - 1) log2 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:
Tr(N) = C � (N - 1) log2 N . (11)
3
Ostatecznie z (8), (9), (10) oraz (11) otrzymujemy:
T (N) = 2C � (N - 1) log2 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
BAL - ćwiczenia nr 6 (algorytmy)
16 grudnia 2010
Algorithm 1 A6.1: Sortowanie przez selekcję
procedura Sort_Selection
WE: T (N)
powtarzaj od i = 1 do N - 1
min �! i
powtarzaj od j = i + 1 do N
jeśli Tj < Tmin
min �! j
zakończ iterację
zamień(Ti, Tmin)
zakończ iterację
WY: T (N)
zakończ procedurę
Algorithm 2 A6.2: Sortowanie  bąbelkowe
procedura Sort_Bubble
WE: T (N)
powtarzaj od i = 1 do N - 1
powtarzaj od j = 1 do N - i
jeśli Tj > Tj+1
zamień(Tj, Tj+1)
zakończ iterację
zakończ iterację
WY: T (N)
zakończ procedurę
1
Algorithm 3 A6.3: Rekurencyjne sortowanie  szybkie
procedura Sort_Quick(T, L, P )
jeśliL < P
S �! L
powtarzaj odi = L + 1doP
jeśliTi < TL
S �! S + 1
zamień(TS, Ti)
zakończ iterację
zamień(TS, TL)
Sort_Quick(T, L, S - 1)
Sort_Quick(T, S + 1, P )
zakończ procedurę
Algorithm 4 A6.4 Ciąg Fibonacciego
funkcja Fib(N )
jeśliN = 0 lub N = 1
WY: N
w p.p.
WY: Fib(N -1) +Fib(N -2)
zakończ funkcję
2
 T (N)
T (N) = N + 1
= O(N) .
F0 = 0
F1 = 1
FN = FN-1 + FN-2 N > 1 .
N < 2
T (N)
FN
T (N)
FN T (N)
T (N)
FN+2 - FN+1 - FN = 0
F0 = 0
F1 = 1
FN = a � bN
a = 0

b = 0, b = 1 .

FN = a1 � bN + a2 � bN
1 2
1
"
a1 =
5
1
a2 = - "
5
"
1+ 5
b1 =
2
"
1- 5
b2 =
2
�ł " N " N łł
1 1 + 5 1 - 5
�ł �ł
FN = " - .
2 2
5
T (N)
T (0) = 0
T (1) = 1
T (N) = T (N - 1) + T (N - 2) + 1 N > 1 .
" N " N
1 + 5 1 - 5
T (N) = C1 + C2 .
2 2
"
N
limN" 1- 5 = 0
2
�ł " N �ł
1 + 5
�ł łł
T (N) = O
2
H" O 1, 62N .
T1 �! 1
T2 �! 1
i = 3 N
Ti �! Ti-1 + Ti-2
TN
T (N)
T (N) = N - 2
= O(N) ,
"
1+ 5
2
 N - 1
1, 628
1, 628 = 1, 62 � 1, 62 � 1, 62 � 1, 62 � 1, 62 � 1, 62 � 1, 62 � 1, 62
= (1, 62 � 1, 62 � 1, 62 � 1, 62)2
2
= (1, 62 � 1, 62)2
2
2
= 1, 622 ,
log2 N
T (N) = C � log2 N
= O(log N) ,