Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Algorytmy i struktury danych

(2) Wydajno´s´c algorytmów

Paweł J. Matuszyk

AGH Kraków

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Plan wykładu

1

Analiza algorytmów

2

Zło˙zono´s´c obliczeniowa

3

Przykłady analizy algorytmów

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Analiza algorytmów

Ka˙zde wykonanie algorytmu na komputerze wymaga
pewnej pracy oraz pewnej ilo´sci miejsca w jego pami ˛eci.

Dlatego projektuj ˛

ac algorytm, powinni´smy odpowiedzie´c

sobie na pytanie:

Czy nasz komputer umo˙zliwia stosowanie rozwa˙zanego

algorytmu dla przewidywanych danych?

Okazuje si ˛e bowiem, ˙ze dla wielu znanych algorytmów
czas ich działania zwi ˛eksza si ˛e zbyt szybko w miar ˛e, jak
wzrasta wielko´s´c danych wej´sciowych.

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Analiza algorytmów

Analiza algorytmu

algorytmów polega na okre´sleniu

zasobów

, jakie potrzebne s ˛

a

do jego wykonania.

Zasoby

czas oblicze ´n

→ zło˙zono´s´c obliczeniowa,

pami ˛e´c

→ zło˙zono´s´c pami ˛eciowa lub wymagania

pami ˛eciowe,

szeroko´s´c kanału komunikacyjnego,

sprz ˛et komputerowy.

Wszystkie te zasoby s ˛

a wyra˙zane jako funkcja

rozmiaru danych

wej´sciowych

.

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Analiza algorytmu

Czas działania

Zachowanie si ˛e algorytmu mo˙ze by´c ró˙zne dla ró˙znych
mo˙zliwych danych wej´sciowych, potrzebujemy ´srodków, do
wyra˙zania tego zachowania w postaci prostych, łatwych do
zrozumienia formuł.

Czas oblicze ´n mierzy si ˛e zazwyczaj liczb ˛

a

(dominuj ˛

acych)

operacji elementarnych

wykonywanych przez procesor w

celu rozwi ˛

azania danego problemu za pomoc ˛

a danego

algorytmu.

Zakłada si ˛e, ˙ze wykonanie pojedynczej i-tej operacji
wymaga czasu c

i

, który jest stały dla danego komputera.

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Analiza algorytmu

Zu˙zycie pami ˛eci

Zu˙zycie pami ˛eci mierzy si ˛e

liczb ˛

a zmiennych

oraz

liczb ˛

a i

rodzajem struktur danych

u˙zytych przez dany algorytm (z

uwzgl ˛ednieniem ich rozmiaru).

Definicja rozmiaru danych wej´sciowych zale˙zy istotnie od
rozwa˙zanego problemu.

Z reguły rozmiarem danych wej´sciowych jest to długo´s´c
(liczba elementów) ci ˛

agu wej´sciowego.

Jednostka: słowo pami ˛eci.
Przykłady definicji rozmiaru problemu:

sortowanie tablicy: długo´s´c tablicy,
problemy grafowe: ilo´s´c w ˛ezłów i kraw ˛edzi,
operacje na wielomianach: stopie ´n wielomianu,
operacje na macierzach: rozmiary macierzy,
operacje arytmetyczne: całkowita liczba bitów,

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Wpływ danych na działanie algorytmu

We wszystkich przypadkach zakładamy taki sam rozmiar
danych wej´sciowych.

Przypadek

optymistyczny

:

dane wej´sciowe s ˛

a takie, ˙ze dany algorytm w minimalnej

liczbie kroków znajduje rozwi ˛

azanie.

Przypadek

pesymistyczny

:

dane wej´sciowe s ˛

a takie, ˙ze dany algorytm znajduje

rozwi ˛

azanie wykonuj ˛

ac najwi ˛eksz ˛

a mo˙zliw ˛

a dla danego

rozmiaru danych ilo´s´c operacji.

Przypadek

´sredni

(

oczekiwany

):

statystycznie najbardziej prawdopodobny — dla losowo
wybranych danych.

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Plan wykładu

1

Analiza algorytmów

2

Zło˙zono´s´c obliczeniowa

3

Przykłady analizy algorytmów

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

W celu okre´slenia zło˙zono´sci obliczeniowej algorytmu,
wyra˙zamy ilo´s´c operacji potrzebnych do rozwi ˛

azania

danego problemu przez algorytm zale˙zno´sci ˛

a

matematyczn ˛

a (np. f (n) = an

2

+

bn + c).

W praktyce interesuje nas

dominuj ˛

acy składnik

we wzorze

na f (n) —

zachowanie asymptotyczne

.

Rz ˛

ad wielko´sci funkcji f (n)

to dominuj ˛

acy składnik w f (n) z pomini ˛eciem stałych

współczynników.

Rz ˛

ad wielko´sci funkcji okre´sla, jak szybko ro´snie funkcja,

gdy ro´snie argument n (n → ∞).

Przewa˙znie mówimy, ˙ze dany algorytm jest lepszy od
innego, je´sli jego pesymistyczny czas działania jest funkcj ˛

a

ni˙zszego rz ˛edu (ALE: nie musi to by´c słuszne dla małych
danych wej´sciowych!).

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Notacja asymptotyczna

Asymptotyczna zło˙zono´s´c algorytmu

to okre´slenie rz ˛edu wielko´sci czasu działania algorytmu, tzn.
okre´slenie szybko´sci wzrostu czasu działania algorytmu, gdy
rozmiar danych d ˛

a˙zy do niesko ´nczono´sci.

W

notacji asymptotycznej

czas działania algorytmów

opisywany jest przez funkcje okre´slone na zbiorze liczb
naturalnych N.
Argument funkcji jest najcz ˛e´sciej rozmiarem danych
wej´sciowych.

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Notacja asymptotyczna

Notacja Θ

Dla danej funkcji g(n) : N → R oznaczamy przez Θ(g(n)) klas ˛e
równowa˙zno´sci funkcji:

Θ(

g(n)) =

{f (n) : ∃c

1

,

c

2

>

0 ∃n

0

∈ N : c

1

g(n) 6 f (n) 6 c

2

g(n) ∀n > n

0

}

Formalnie, zachodzi wtedy:

f (n) ∈ Θ(g(n))

Zazwyczaj pisze si ˛e jednak:

f (n) = Θ(g(n))

Notacja Θ jest

asymptotycznie

dokładnym

oszacowaniem:

ogranicza funkcj ˛e od góry i od dołu

.

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Notacja asymptotyczna

Przykład

Dana jest funkcja

f (n) = an

2

+

bn + c,

gdzie a > 0, b i c s ˛

a stałymi.

Odrzucaj ˛

ac składniki ni˙zszego rz ˛edu otrzymujemy

f (n) = Θ(n

2

).

Wynika to z faktu, ˙ze:

c

1

=

a/4

c

2

=

7a/4

n

0

=

2 max



|b| /a,

p|c| /a



Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Notacja asymptotyczna

Notacja O

Dla danej funkcji g(n) : N → R oznaczamy przez O(g(n)) klas ˛e
równowa˙zno´sci funkcji:

O(g(n)) = {f (n) : ∃c > 0 ∃n

0

∈ N : 0 6 f (n) 6 cg(n) ∀n > n

0

}

Notacja O jest

asymptotyczn ˛

a

granic ˛

a górn ˛

a

:

szacuje pesymistyczny czas
działania algorytmu

.

Θ(

g(n)) ⊆ O(g(n))

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Notacja asymptotyczna

Notacja Ω

Dla danej funkcji g(n) : N → R oznaczamy przez Ω(g(n)) klas ˛e
równowa˙zno´sci funkcji:

Ω(

g(n)) = {f (n) : ∃c > 0 ∃n

0

∈ N : 0 6 cg(n) 6 f (n) ∀n > n

0

}

Notacja Ω jest

asymptotyczn ˛

a

granic ˛

a doln ˛

a

:

szacuje czas działania algorytmu
dla

najlepszego przypadku

.

Θ(

g(n)) ⊆ Ω(g(n))

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Notacja asymptotyczna

Własno´sci

Przechodnio´s´c

f (n) = Θ(g(n))

∧

g(n) = Θ(h(n))

⇒

f (n) = Θ(h(n))

f (n) = O(g(n))

∧

g(n) = O(h(n))

⇒

f (n) = O(h(n))

f (n) = Ω(g(n))

∧

g(n) = Ω(h(n))

⇒

f (n) = Ω(h(n))

Zwrotno´s´c

f (n) = Θ(f (n))

f (n) = O(f (n))

f (n) = Ω(f (n))

Symetria

f (n) = Θ(g(n))

⇐⇒

g(n) = Θ(f (n))

Symetria transpozycyjna

f (n) = O(g(n))

⇐⇒

g(n) = Ω(f (n))

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Notacja asymptotyczna

Twierdzenie

Dla ka˙zdych dwóch funkcji f (n) i g(n) zachodzi:

f (n) = Θ(g(n)) ⇐⇒ f (n) = Ω(g(n)) ∧ f (n) = Ω(g(n))

Twierdzenie

Dla ka˙zdego wielomianu f (n) ∈ P

k

zachodzi:

f (n) = Θ(n

k

)

f (n) = O(n

k

)

f (n) = Ω(n

k

)

Twierdzenie

O(1) ⊂ O(lgn) ⊂ O(n) ⊂ O(nlgn) ⊂ O(n

2

) ⊂ O(

2

n

) ⊂ O(

n!) ⊂ O(n

n

)

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Notacja asymptotyczna

Porównanie rz ˛edów

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Porównanie szybko´sci wzrostu funkcji

n

log n

n

n log n

n

2

n

3

2

n

10

0.003µs

0.01µs

0.033µs

0.10µs

1.0µs

1µs

20

0.004µs

0.02µs

0.086µs

0.40µs

8.0µs

1 ms

30

0.005µs

0.03µs

0.147µs

0.90µs

27.0µs

1 s

40

0.005µs

0.04µs

0.213µs

1.60µs

64.0µs

18.3 min

50

0.006µs

0.05µs

0.282µs

2.50µs

125.0µs

13 d

10

2

0.007µs

0.10µs

0.664µs

10µs

1 ms

4 · 10

13

l

10

3

0.010µs

1.00µs

9.966µs

1 ms

1 s

10

4

0.013µs

10.0µs

130µs

100 ms

16.7 min

10

5

0.017µs

0.10 ms

1.67 ms

10 s

11.6 d

10

6

0.020µs

1.00 ms

19.930 ms

16.70 min

31.7 l

10

7

0.023µs

0.01 s

2.660 s

1.16 d

31709 l

10

8

0.027µs

0.10 s

2.660 s

115.70 d

3.17 · 10

7

l

10

9

0.030µs

1.00 s

29.900 s

31.70 l

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Wykaz podstawowych zło˙zono´sci czasowych

log n

algorytmy, w których zadanie o rozmiarze n sprowadzane jest do
zadania rozmiaru n/2, plus pewna stała liczba działa ´n;

n

algorytmy, w których dla ka˙zdego z n elementów (danych
wej´sciowych) wykonywana jest stała liczba działa ´n;

n log n

algorytmy, w których zadanie o rozmiarze n zostaje
sprowadzone do dwóch podzada ´n rozmiaru n/2, plus pewna
liczba działa ´n liniowa wzgl ˛edem rozmiaru n, potrzebnych do
wykonania najpierw podzielenia, a nast ˛epnie scalenia rozwi ˛

aza ´n

podzada ´n rozmiaru n/2 w rozwi ˛

azanie rozmiaru n;

n

2

algorytmy, w których jest wykonywana pewna stała liczba
działa ´n dla ka˙zdej pary danych wej´sciowych (podwójna iteracja);

n

k

algorytmy o k wzajemnie zagnie˙zd˙zonych p ˛etlach;

2

n

algorytmy, w których jest wykonywana stała liczba działa ´n, dla
ka˙zdego podzbioru danych wej´sciowych;

n!

algorytmy, w których jest wykonywana stała liczba działa ´n, dla
ka˙zdej permutacji danych wej´sciowych.

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Dolne i górne ograniczenia

Znalezienie algorytmu
rozwi ˛

azania danego problemu

ustanawia

górne ograniczenie

dla tego zadania
algorytmicznego.

Je˙zeli dolne i górne ograniczenia
s ˛

a sobie równe z dokładno´sci ˛

a

do stałych, to problem w sensie
notacji O jest

zamkni ˛ety

.

Je˙zeli dolne i górne ograniczenia
si ˛e nie schodz ˛

a, to mówimy o

istnieniu

luki algorytmicznej

.

Przykład problemu, który nie jest zamkni ˛ety

Problem minimalnego drzewa rozpinaj ˛

acego.

Udowodniono, ˙ze zadanie to wymaga O(n) czasu, gdzie n jest liczb ˛

a

kraw ˛edzi grafu, ale nie ma algorytmu, który realizowałby to zadanie w
czasie liniowym.

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Plan wykładu

1

Analiza algorytmów

2

Zło˙zono´s´c obliczeniowa

3

Przykłady analizy algorytmów

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Bubble-sort

for

(i = 1; i < N; ++i)

//(1)

for

(j = N - 1; j > i; --j)

//(2)

if

(t[j] < t[j - 1])

swap(t[j], t[j - 1]);

Analiza kosztu czasowego zagnie˙zd˙zonych p ˛etli (dla
sortowania b ˛

abelkowego):

p ˛etla zewn ˛etrzna (1) wykona si ˛e N razy,

p ˛etla wewn ˛etrzna (2) wykona si ˛e ´srednio (N − 1)/2 razy,

a zatem koszt czasowy wykonania algorytmu wynosi:

T (n) = N · (N − 1)/2

⇒

T (n) = O(N

2

)

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Insert-sort

for

(j = 1; j < N; ++j){

// (1), c1

x = t[j];

//

c2

for

(i = j-1; i>=0 && T[i]>x; --j)

// (2), c3

t[i + 1] = t[i];

//

c4

t[i + 1] = x;

//

c5

}

Analiza kosztu czasowego zagnie˙zd˙zonych p ˛etli (dla
sortowania przez wstawianie):

p ˛etla zewn ˛etrzna (1) wykona si ˛e N − 1 razy,
p ˛etla wewn ˛etrzna (2) wykona si ˛e w j-tej iteracji t

j

6 j razy,

a zatem koszt czasowy wykonania algorytmu wynosi:

T (n) = (N − 1)(c

1

+

c

2

+

c

5

) + (

c

3

+

c

4

)

N−1

X

j=1

t

j

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Insert-sort

for

(j = 1; j < N; ++j){

// (1), c1

x = t[j];

//

c2

for

(i = j-1; i>=0 && T[i]>x; --j)

// (2), c3

t[i + 1] = t[i];

//

c4

t[i + 1] = x;

//

c5

}

Analiza kosztu czasowego zagnie˙zd˙zonych p ˛etli:

Przypadek optymistyczny

(tablica wst ˛epnie posortowana) — dla

ka˙zdego j zachodzi

t[i] < x

→ t

j

=

1, czyli:

T (n) = (N − 1)(c

1

+

c

2

+

c

5

) + (

c

3

+

c

4

)(

N − 1) · 1

⇒

T (n) = O(N)

Przypadek pesymistyczny

(tablica posortowana odwrotnie) — dla

ka˙zdego i porównujemy

T[i]

z

T[i+1]

→ t

j

=

j, czyli:

T (n) = (N − 1)(c

1

+

c

2

+

c

5

) + (

c

3

+

c

4

)

N−1

X

j=1

j

= (

N − 1)(c

1

+

c

2

+

c

5

) + (

c

3

+

c

4

)(

N(N − 1)/2) ⇒

T (n) = O(N

2

)

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Merge-sort

merge_sort(ELEM t[],

int

p,

int

k) {

if

(p < k) {

q =(p + k) / 2;

merge_sort(t, p, q);

merge_sort(t, q + 1, k);

merge(T, p, q, k);

}

}

Je´sli rozmiar danych jest
wystarczaj ˛

aco mały,

n 6 c ⇒ T (n) = Θ(1).

Problem jest podzielony na 2
podproblemy, ka˙zdy o
rozmiarze n/2.

T (n) =



Θ(

1)

n 6 c

2T (n/2) + Θ(1) + Θ(n)

n > c

D(n) = Θ(1) – czas podziału
na podproblemy,

C(n) = Θ(n) – czas scalania
rozwi ˛

aza ´n podproblemów w

pełne rozwi ˛

azanie.

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Metoda rekurencji uniwersalnej

Równanie rekurencyjne:

T (n) = aT (n/b) + f (n)

a > 1, b > 1, f (n) > 0

Algorytm dzieli problem rozmiaru n na a podproblemów ka˙zdy o
rozmiarze n/b.

Ka˙zdy podproblem jest rozwi ˛

azywany rekurencyjnie w czasie

T (n/b).

Koszt dzielenia problemu oraz ł ˛

aczenia rezultatów cz ˛e´sciowych

jest opisany funkcj ˛

a f (n).

T (n) mo˙ze by´c ograniczone asymptotycznie:

f (n) = O(n

log

b

a−

)

⇒

T (n) = Θ(n

log

b

a

)

f (n) = Θ(n

log

b

a

)

⇒

T (n) = Θ(n

log

b

a

log n)

f (n) = Ω(n

log

b

a+

) ∧

af (n/b) 6 cf (n)

⇒

T (n) = Θ(f (n))

gdzie:  > 0, c < 1, a ostatni warunek zachodzi dla wszystkich
dostatecznie du˙zych n.

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Metoda rekurencji uniwersalnej

f (n) = O(n

log

b

a−

)

T (n) = Θ(n

log

b

a

)

f (n) = Θ(n

log

b

a

)

T (n) = Θ(n

log

b

a

log n)

f (n) = Ω(n

log

b

a+

) ∧

af (n/b) 6 cf (n)

T (n) = Θ(f (n))

W ka˙zdym z trzech przypadków porównujemy f (n) z funkcj ˛

a

n

log

b

a

— wi ˛eksza funkcja decyduje o zło˙zono´sci algorytmu

rekurencyjnego.

W pierwszym przypadku f (n)

musi by´c wielomianowo mniejsza

ni˙z n

log

b

a

.

W trzecim przypadku f (n)

musi by´c wielomianowo wi ˛eksza

ni˙z

n

log

b

a

oraz spełnia´c warunek regularno´sci af (n/b) 6 cf (n).

Jest pewna luka pomi ˛edzy przypadkami 1 i 2 oraz 2 i 3 (funkcje,
które nie s ˛

a wielomianowo mniejsze) — wtedy nie mo˙zna

zastosowa´c metody rekurencji uniwersalnej.

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Merge-sort

Sortowanie przez wstawianie:

T (n) =



Θ(

1)

n 6 c

2T (n/2) + Θ(1) + Θ(n)

n > c

Mamy zatem: a = b = 2 oraz f (n) = cn, n

log

2

2

=

n

1

=

n, czyli

f (n) = Θ(n), mamy przypadek drugi.

A zatem:

T (n) = Θ(n

log

2

2

log n) = Θ(n log n)

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Powłoka wypukła dla n punktów na płaszczy´znie

Uwaga: odcinek ł ˛

acz ˛

acym dwa punkty stanowi

cz ˛e´s´c powłoki wypukłej wtw gdy wszystkie
pozostałe punkty le˙z ˛

a po tej samej stronie

przedłu˙zenia tego odcinka do całej prostej.

Algorytm I

: we´z ka˙zdy potencjalny odcinek i

sprawd´z, czy wszystkie pozostałe n − 2 punkty
le˙z ˛

a po tej samej jego stronie.

Algorytm II

:

1

Znajd´z "najni˙zszy" punkt P

1

.

2

Posortuj pozostałe punkty wg k ˛

ata, jaki tworz ˛

a te punkty

poł ˛

aczone z P

1

z lini ˛

a poziom ˛

a. Niech P

2

. . . P

n

b ˛edzie tak

powstał ˛

a list ˛

a.

3

Zacznij od punktów P

1

i P

2

jako nale˙z ˛

acych do bie˙z ˛

acej powłoki.

4

Powtarzaj dla i = 3 . . . n:

1

Dodaj na prób ˛e punkt P

i

do bie˙z ˛

acej powłoki,

2

Przejd´z wstecz przez odcinki bie˙z ˛

acej powłoki, usuwaj ˛

ac punkty P

j

,

je´sli dwa punkty P

1

i P

i

, znajduj ˛

a si ˛e po przeciwległych stronach

prostej przechodz ˛

acej przez P

j−1

i P

j

i ko ´ncz ˛

ac proces

przechodzenia wstecz w momencie napotkania takiego j, dla
którego punktu P

j

nie trzeba usuwa´c.

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Powłoka wypukła dla n punktów na płaszczy´znie

Analiza algorytmów

Zło˙zono´s´c obliczeniowa

Przykłady analizy algorytmów

Powłoka wypukła dla n punktów na płaszczy´znie

Algorytm I:

Danych jest n punktów, dla których istnieje n

2

odcinków i z

ka˙zdym z nich nale˙zy sprawdzi´c n − 2 punkty,

→

całkowity czas działania: O(n

3

)

.

Algorytm II:

1

Wyszukiwanie — O(n),

2

Sortowanie — O(n log n).

3

O(1).

4

O(n) (punkt mo˙ze by´c usuni ˛ety co najwy˙zej raz; p ˛etla wew.
zatrzymuje si ˛e, gdy napotka punkt, którego nie trzeba
usuwa´c).

→

całkowity czas działania: O(n log n).