Zajęcia nr 2/3

 

Analiza wydajności algorytmów 

– złożoność i jej miary

Algorytmy i struktury danych

Prowadzący

:  

dr hab.inż. ANDRZEJ WALCZAK, 

prof.WAT

 

 

Złożoność obliczeniowa algorytmów 

-

 

analiza algorytmów               

   

• Analiza algorytmów - złożoność obliczeniowa jest podstawową 

własnością  określaną  dla  algorytmów.  Zadaniem  analizy 

algorytmu  jest  określenie  tej  złożoności,  a  co  za  tym  idzie 

określenie realizowalności algorytmu oraz jego wydajności.. 

• Algorytmy 

realizowalne 

mają 

najczęściej 

złożoność 

aproksymowaną funkcją:

– liniową (wielomianem)
– logarytmiczną.

Mówi  się,  że  takie  algorytmy  określają  zadania  ze  zbioru 

zadań 

rozwiązywalnych 

(a 

co 

za 

tym 

idzie 

implementowalnych). Najszybsze są algorytmy o złożoności 

logarytmicznej.

• Nie  potrafimy  skutecznie  implementować  algorytmów  o 

złożoności wykładniczej. 

 

 

Rodzaje złożoności algorytmów

• Złożoność zasobowa (pamięciowa) - wyrażana w skali 

zajętości zasobów (PAO, pamięci zewnętrznych itp.) 
niezbędnych dla realizacji algorytmu

• Złożoność czasowa - wyrażana w skali czasu wykonania 

algorytmu (liczba kroków, aproksymowany czas 
rzeczywisty)

• Przykłady szacowania wartości złożoności algorytmów 

będziemy realizować przy okazji konkretnych 
przykładów na kolejnych wykładach

• De facto wszystko przenosi się w konsekwencji na 

koszty eksploatacji oprogramowania, realizującego 
analizowany algorytm

 

 

Czynniki wpływające na  złożoność 

algorytmów

• Rozmiar  zadania  - rozmiar danych niezbędnych dla 

realizacji algorytmu. Bierze się pod uwagę:

– rozmiar danych wejściowych
– rozmiar danych roboczych
– rozmiar danych wyjściowych

• Czas działania algorytmu - liczba kroków przekładająca 

się na czas faktycznej pracy maszyny realizującej 
algorytm. Istotne znaczenie mają w tym przypadku:

– złożoność obliczeniowa rozwiązywanego zadania
– sposób konstrukcji algorytmu
– wydajność maszyny realizującej obliczenia

 

 

Funkcja kosztu algorytmu

• Funkcja kosztu zasobowego algorytmu stanowi odwzorowanie 

rozmiaru zadania w umowne jednostki kosztu algorytmu (np. 
rozmiar zasobów, jednostki monetarne (złotówki, dolary itp.)):

– FKz : RZ -> WKz, gdzie:  FKz - funkcja kosztu zasobowego,

   

RZ -  rozmiar zadania,

WKz - wartość kosztu zasobowego,

Dla potrzeb wykładu pozostaniemy jedynie przy 

kosztach zasobowych algorytmów.

• Jednak nie tylko koszty zasobowe są brane pod uwagę. Często 

analizuje się inne koszty realizacji algorytmów (np. pieniądze).

 Przejrzyj ponownie slajdy z analizą efektywności algrytmu 

Fibonacciego. Co możesz powiedzieć na temat jego 
złożoności obliczeniowej?

 

 

Asymptotyczna złożoność 

algorytmów 

• Asymptotyczna oznacza, że dla dostatecznie dużych danych 

wejściowych n liczymy tylko rząd wielkości czasu działania 
algorytmu;

• Zapiszmy formalnie asymptotyczną górną granicę 

(pesymistyczny czas działania algorytmu):

•

O( g(n) ) = { f(n): 0 <= f(n) <=  c*g(n), c > 0, n > N}

•

Jest to przykład tak zwanej notacji dużego O. Fakt, że 
dana wielkość jest rzędu f zapisujemy symbolicznie 
jako O(f).

•

W zapisie formalnym złożoności wskazano, że 
złożoność zależy od liczby przetwarzanych danych n.

 

 

Przykłady asymptotycznej 

złożoności algorytmów 

• W praktyce, większość algorytmów ma złożoność zaliczaną do 

jednej z poniższych klas: 

– log n, czyli złożoność logarytmiczna. Podstawa logarytmu 

nie ma tu znaczenia, gdyż jej zmiana oznacza jedynie 

przemnożenie przez stałą.

– n, n

2

, ..., czyli złożoność liniowa, kwadratowa, sześcienna 

lub inaczej złożoność wielomianowa, gdyż funkcje te są 

wielomianami zmiennej n. Problemy dla których istnieją 

algorytmy o złożonosci co najwyżej wielomianowej, 

nazywane są problemami typu P (ang. polynomial, czyli 

wielomian).  Jest to bardzo ważna klasa algorytmów, gdyż 

algorytmy które mają złożoność czasową co najwyżej 

wielomianową, (czyli są O(n

k

), k=1,2,...) dają się w 

użytecznym czasie wykonać na komputerach dla większości 

rzeczywistych problemów. 

– n log n czyli złożoność liniowo logarytmiczna. 

– n

log n

 , czyli złożoność podwykładnicza 

– 2

n

 , czyli złożoność wykładnicza 

– n!, czyli złożoność wykładnicza n! 

 

 

Przykłady asymptotycznej 

złożoności algorytmów 

• Pojedyncza instrukcja

– s1; s2; …. ; sk

• O(1)  dopóki k jest stałą 

• Pojedyncza pętla

– for(i=0;i<n;i++) { s; }

• Założenie: s jest O(1)
• Złożoność czasowa jest:   n O(1)   lub   O(n)

• Zagnieżdżona pętla:

– for(i=0;i<n;i++)

   for(j=0;j<n;j++) { s; }

– Złożoność jest:  n O(n)   lub   O(n

2

)

 

 

Analiza wydajności algorytmów 

– złożoność i jej miary

• Do opisu wydajności (złożoności) algorytmów używa się 

najczęściej tzw. O notacji. Opisuje ona górne 
ograniczenie funkcji z dokładnością do czynnika stałego.

• Wydajność algorytmu rozumiemy ogólnie jako liczbę 

operacji wykonywanych w algorytmie w zależności od 
liczby przetwarzanych danych. Jeśli dane mają rozmiar n 
to złożoność algorytmu zapiszemy jako pewną funkcję 
f(n).

• Notacje O rozumiemy jako wskazanie funkcji g(n) takiej, 

że istnieje takie n

0

, że dla n>n

0

 zawsze f(n)<cg(n) gdzie 

c jest stałą. Notacja O wskazuje nam wiec majorantę 
albo inaczej ograniczenie górne funkcji złożoności 
algorytmu.

 

 

Analiza wydajności algorytmów 

– złożoność i jej miary

• Symetrycznie do O-notacji stosuje się  

 -notację, która oznacza ograniczenie 
złożoności od dołu czyli minorantę.

• Notacje  rozumiemy jako wskazanie 

funkcji g(n) takiej, że istnieje takie n

0

, 

że dla n>n

0

 zawsze f(n)>cg(n) gdzie c 

jest stałą. Notacja  wskazuje nam wiec 

minorantę albo inaczej ograniczenie 
dolne funkcji złożoności algorytmu.

 

 

Analiza wydajności algorytmów 

– złożoność i jej miary

• Łatwo zauważyć, że definicje złożoności 

mają  charakter  asymptotyczny  co 
oznacza, że rozumiemy je jako zdążanie 
złożoności 

algorytmu 

do 

funkcji 

wskazanej  przez  O-notację  albo  -

notację  przy  odpowiednio  dużej  liczbie 
zmiennych 

w 

algorytmizowanym 

zdaniu.

 

 

Reguły O-notacji 

• Oceniając liczbę operacji w algorytmie możemy 

pominąć składniki stałe wobec składników 
zależnych od n bo wraz ze wzrostem n udział 
składników stałych będzie tak mały, że możemy go 
zaniedbać. Podobnie w oszacowaniu złożoności 
możemy uzasadnić pomijanie czynników stałych. 
Jeśli algorytm zawiera kilka składowych 
elementów, z których każdy wnosi swoją złożoność 
tak, że możemy skonstruować funkcję f(n) = 
n

3

+n

2

+n+..., to do oceny majoranty g(n) bierzemy 

tylko składnik o najwyższym wykładniku.

 

 

Formalizm O-notacji 

• Składniki stałe zapisujemy jako O(1) czyli 

O(const) = O(1)

• Pomijamy czynniki stałe O(const*f) = c O(f) = O(f)
• Dodawanie elementów składowych jest 

uwzględniane przez wybranie składnika o 
najwyższej potędze O(f

1

) + O(f

2

) = O(f

1

 +f

2

) = 

max(O(f

1

), O(f

2

))

• Jeśli mnożone są elementy składowe o różnej 

złożoności to mnożenie ulega zachowaniu O(f

1

) 

O(f

2

) = O(f

1

*f

2

)

 

 

Przykłady O-notacji

złożonoś

ć

przykład

O(1)

Pobieranie pierwszego elementu ze 

zbioru danych

O(lg n)

Podział n elementowego zbioru na 

pół, następnie podział części na pół 
itd.

O(n)

Przeglądanie zbioru n danych

 

 

Przykłady O-notacji

złożonoś

ć

przykład

O(n lg n) Kolejne podziały zbioru na pół 

połączone z ich przeszukiwaniem

O(n

2

)

Przeglądanie zbioru n 

elementowego raz dla każdego 

elementu z innego równolicznego 

zbioru danych

O(2

n

)

Generowanie wszystkich możliwych 

podzbiorów zbioru n danych

 

 

Inne typy notacji złożoności 

algorytmów

• Definicja:  funkcja  f(n)  ma  złożoność 



(g(n))  wtedy,  kiedy  istnieją  dwie 

dodatnie  liczy  c  oraz  N  takie,  że 
f(n)>=cg(n) dla wszystkich n>=N.

• Widać, że g(n) jest ograniczeniem f(n) z 

dołu, czyli minorantą badanej funkcji.

 

 

Inne typy notacji złożoności 

algorytmów

• Definicja: f(n) ma złożoność 



(g(n)), jeśli istnieją dodatnie 

liczby c

1

, c

2

 oraz N takie, że 

c

1

g(n)=<f(n)=<c

2

g(n) dla 

wszystkich n>=N.

• Czyli szukamy w tej notacji funkcji 

g(n) takiego samego rzędu jak f(n)

 

 

Inne typy notacji złożoności 

algorytmów

• Po  co  są  wprowadzane  różne  typy 

notacji?  Otóż  dlatego,  że  notacja 
za pomocą majoranty O(f(n)) może 
prowadzić  do  uznania  niektórych 
algorytmów  za  zbyt  złożone, 
podczas, gdy w notacji 



(f(n)) albo 



(f(n))  mogą  zostać  przyjęte  za 

wystarczająco wydajne.

 

 

Złożoność pesymistyczna, 

optymistyczna i średnia

• Przykład: Złożoność wyszukiwania elementu 

w  tablicy  n-elementowej.  Możemy  trafić  od 

razu  –  przypadek  najlepszy-  element 

szukany  to  T[0]  i  złożoność  otrzymana  to 

O(1), albo po przeszukaniu całej tablicy czyli 

element szukany to T[n] i złożoność O(n). 

• Mówimy,  że  złożoność  pesymistyczna  to 

taka, 

która 

poprzez 

zadanie 

danych 

wejściowych  do  algorytmu  powoduje,  że 

wykona  się  on  maksymalną  możliwą  liczbę 

razy. 

 

 

Złożoność pesymistyczna, 

optymistyczna i średnia

• Złożoność optymistyczna to ten przypadek, 

w  którym  „trafiamy  najszybciej  jak  można 
w  rozwiązanie”.  Każdy  z  przypadków 
zależy od doboru danych wejściowych. Czy 
możemy  ich  dobór  przewidzieć  „a  priori” 
czyli przed eksperymentem?

• Definiuje  się złożoność  średnią ulokowaną 

pomiędzy  przypadkiem  skrajnie  złym  i 
skrajnie dobrym

 

 

Złożoność pesymistyczna, 

optymistyczna i średnia

• Oznaczmy  przez  p  prawdopodobieństwo,  że 

element  x  znajduje  się  w  tablicy  i  załóżmy,  że 
wszystkie  lokalizacje  elementu  x  są  jednakowo 
prawdopodobne. Czyli z prawdopodobieństwem 
1-p element w tablicy nie występuje. Oznaczmy 
przez  Z 

i,  n

  zbiór  takich  i,  że  0<i<n  oraz  x 

znajduje się na i-tym miejscu w tablicy. Przez Z 

n,n

 oznaczymy zbiór, w którym x jest nieobecne. 

Wobec założeń zapiszemy:

• P(Z 

i,n

 ) = p/n oraz P(Z 

n,n

) = 1-p 

 

 

Złożoność pesymistyczna, 

optymistyczna i średnia

• Złożoność odpowiednią algorytmu oznaczymy 

jako:

• f(Z 

i,n

) = i oraz f(Z 

n,n

) = n

• Średnia złożoność algorytmu w analizowanym 

przykładzie to:



 















2

1

1

1

1

,

1

,

p

n

n

p

n

p

i

n

p

Z

f

Z

P

f

n

i

i

n

N

i

i

n

average





































n

i

n

n

i

1

2

1

 

 

• Z definicji złożoności w przypadku 

średnim widać, że jest ona 
równoznaczna z pojęciem wartości 
oczekiwanej statystycznie

Złożoność pesymistyczna, 

optymistyczna i średnia

   

i

n

n

i

i

n

average

Z

f

Z

P

f

,

0

,







 

 

Złożoność pesymistyczna, 

optymistyczna i średnia

• Jeśli element znajduje się w tablicy czyli 

p=1, to średnia złożoność w 
analizowanym przykładzie wynosi: 

• f = (n+1)/2.

• Tylu kroków średnio wymaga znalezienie 

elementu  poszukiwanego  wtedy,  kiedy 
prawdopodobieństwa  znalezienia  dla 
każdego losowania są jednakowe.

• O  jakim  rodzaju  złożoności  powinniśmy 

mówić kiedy analizujemy O-notację?

 

 

Złożoność zamortyzowana

• Widoczne  było  w  przykładzie,  że  dane 

wpływają  na  złożoność  algorytmu.  A  co 

będzie  w  przypadku  algorytmów,  w  których 

poszczególne  ich  części  (podprogramy) 

zmieniają 

dane 

wykorzystywane 

w 

pozostałych? 

Przykładowo 

jeśli 

przeszukiwana  tablica  będzie  wcześniej 

posortowana 

czyli 

uporządkuje 

swoje 

elementy 

rosnąco 

lub 

malejąco, 

to 

znalezienie  elementu  wybranego  będzie  z 

pewnością  trwało  krócej.  Mówimy,  że 

złożoność 

zostanie 

w 

takiej 

sytuacji 

zamortyzowana.

 

 

Złożoność zamortyzowana

• Analiza  w  przypadku  zamortyzowanym  nie 

jest  więc  analizą  złożoności  pojedynczego 
algorytmu  ale  analizą  sekwencji  (albo 
ogólniej  zbioru)  kilku  algorytmów.  W 
najprostszym 

przybliżeniu 

możemy 

przyjmować, 

że 

oszacowana 

złożoność 

zamortyzowana jest sumą złożoności każdego 
z algorytmów występującego w analizowanej 
sekwencji. Można tak przyjąć wówczas, kiedy 
poszczególne 

algorytmy 

są 

od 

siebie 

niezależne i współpracują sekwencyjnie.

 

 

Złożoność zamortyzowana

• Wiemy,  że  złożoność  zależy  od  postaci 

danych  wejściowych.  Definiuje  się  funkcję 

nazywaną  funkcją  potencjału  danych, 

która przypisuje danym i-tego rodzaju liczbę 

określającą  koszty  operacji  na  tych  danych. 

Wówczas zamortyzowany koszt operacji i-tej 

zapiszemy: 

• kosztAmort(op

i

)=koszt(op

i

)+f.potencjału 

(ds

i

)-f.potencjału(ds

i-1

)

• Jeśli  mamy  m  takich  operacji  to  koszt 

zamortyzowany  jest  sumą  kosztów  dla 

wszystkich m operacji

 

 

Techniki wyznaczania złożoności nie 

zamortyzowanych

• Budowanie 

funkcji 

f(n) 

zależności 

pomiędzy liczbą danych n, a liczbą operacji 

w 

algorytmie 

w 

formie 

tabeli 

przyporządkowania 

(pokazano 

przy 

analizie  rekurencji  Fibonacciego  jako 

liczbę podstawień i liczbę dodawań).

• Tworzenie 

postaci 

kombinatorycznej 

funkcji  dyskretnej  f(n)  na  podstawie  ww. 

tabeli  lub  innych  danych  z  matematyki 

dyskretnej  i  ocena  majoranty    O(g(n))  dla 

tej funkcji (albo innego wariantu notacji).

• Metoda równań rekurencyjnych.

 

 

Równania rekurencyjne

• DEFINICJA

• RÓWNANIE POSTACI 

JAK PO PRAWEJ 

NAZYWAMY 

RÓWNANIEM 

REKURENCYJNYM, 

HOMOGENICZNYM ZE 

STAŁYMI 

WSPÓŁCZYNNIKAMI ze 

względu na t.

• Liniowe bo t występuje 

tylko w pierwszej potędze

• Homogeniczne bo prawa 

strona jest równa zeru

0

...

1

1

0













k

n

k

n

n

t

a

t

a

t

a

 

 

Równania rekurencyjne - przykład

• Szereg 

Fibonacciego 
opisuje rekurencja 
podana obok

• Pierwsze równanie 

możemy zapisać 
jako homogeniczne, 
liniowe równanie 
rekurencyjne

1

0

1

0

2

1













t

t

t

t

t

n

n

n

0

2

1











n

n

n

t

t

t

 

 

Równania rekurencyjne

• DEFINICJA

• JEŻELI DANE JEST 

RÓWNIANIE 
REKURENCYJNE TO 
JEGO RÓWNANIEM 
CHARAKTERYSTYCZNY
M NAZYWAMY 
WIELOMIAN ZMIENNEJ 
 r ZAPISANY OBOK 
(czyli metoda 
podstawiania)

0

...

0

1

1

0











r

a

r

a

r

a

k

k

k

0

...

1

1

0













k

n

k

n

n

t

a

t

a

t

a

 

 

Równania rekurencyjne

• DEFINICJA

• ROZWIAZANIEM 

LINIOWEGO, 
HOMOGENICZNEGO 
RÓWNANIA 
REKURENCYJNEGO 
WYRAZONEGO W 
FORMIE 
WIELOMIANOWEJ JEST 
KOMBINACJA LINIOWA 
POTĘG ZMIENNEJ r.

n

k

k

n

n

n

r

c

r

c

r

c

t









...

2

2

1

1

0

...

0

1

1

0











r

a

r

a

r

a

k

k

k

0

...

1

1

0













k

n

k

n

n

t

a

t

a

t

a

 

 

Równania rekurencyjne

• Szereg 

Fibonacciego ma 
równanie 
charakterystyczn
e jak obok

1

0

1

1

0

2

1















t

t

n

gdy

t

t

t

n

n

n

0

1

2





 r

r

 

 

Równania rekurencyjne

• Rozwiązanie dla t

n

 ma 

postać jak obok. 
Współczynniki c

1

 i c

2

 

określamy z 
pozostających równań 
rekurencji Fibonacciego 
dla elementu przy n=0 
oraz n=1.

• Takie dodatkowe 

równania nazywamy 
warunkami 
początkowymi

n

n

n

c

c

t











 













 



2

5

1

2

5

1

2

1

 

 

Równania rekurencyjne

• Warunki 

początkowe dla 
rekurencji 
Fibonacciego 
mają postać jak 
obok

0

2

0

1

0

2

5

1

2

5

1











 













 



c

c

t

1

2

1

1

2

5

1

2

5

1











 













 



c

c

t

n

0

2

1



 c

c

1

2

5

1

2

5

1

2

1













 













 

c

c

 

 

Równania rekurencyjne

• Ostateczna forma 

rozwiązania 

powoduje, że wraz ze 

wzrostem n rośnie 

dokładność 

potrzebna do 

wyrażenia 

pierwiastka z 5. 

Widać także 

jednoznacznie, że 

jest to funkcja 

wykładnicza.

5

1

,

5

1

2

1







c

c









5

2

5

1

2

5

1

n

n

n

t











 













 



 

 

Równania rekurencyjne

• DEFINICJA

• RÓWNANIE POSTACI JAK PO 

PRAWEJ NAZYWAMY 

RÓWNANIEM 

REKURENCYJNYM, 

NIEHOMOGENICZNYM ZE 

STAŁYMI 

WSPÓŁCZYNNIKAMI ze 

względu na t. Funkcja f(n) jest 

dowolna.

• Liniowe bo t występuje tylko 

w pierwszej potędze

• niehomogeniczne bo prawa 

strona  nie jest równa zeru

• NIE ISTNIEJE OGÓLNA 

METODA ANALITYCZNA 

ROZWIAZYWANIA TAKICH 

RÓWNAŃ

• Pokazać można rozwiązania 

m.in.. Dla przypadku gdy 

równanie da się sprowadzić do 

postaci pokazanej obok gdzie 

b to stałą a p(n) to wielomian.

 

n

f

t

a

t

a

t

a

k

n

k

n

n













...

1

1

0

 

n

p

b

t

a

t

a

t

a

k

n

k

n

n













...

1

1

0

 

 

Równania rekurencyjne

• Jest to przykład 

równania 
rekurencyjnego 
liniowego 
niehomogenicznego z 
warunkami 
początkowymi. Po 
stronie prawej mamy 
stałą a więc jest to 
przypadek 
rozwiązywalny.

4

0

1

4

3

1

0

1













t

t

n

dla

t

t

n

n

n

 

 

Równania rekurencyjne

• Jeśli zastąpić w nim n przez 

n-1 to jest to równoważne 
podzieleniu  każdej ze stron 
przez 4. Albo inaczej, 
ponieważ pierwsze równanie 
jest prawdziwe także dla 
n=n+1, to dzieląc je przez 4 
otrzymamy postać drugą, 
która jest równoważna 
pierwszej. Ponieważ wyniki 
są sobie równoważne to 
odejmowanie otrzymanych 
równań stronami musi dać 
równanie homogeniczne, 
którego sposób 
rozwiązywania już znamy.

0

3

4

7

4

4

4

3

4

4

3

2

1

1

1

1

2

1





























n

n

n

n

n

n

n

n

n

t

t

t

t

t

t

t

 

 

Równania rekurencyjne

• Po pomnożeniu przez 4:

0

12

7

2

1











n

n

n

t

t

t







0

4

3

12

7

2













r

r

r

r

n

n

n

c

c

t

4

3

2

1





 

n

n

n

t

t

t

3

4

4

;

4

;

0

1

1

0











 

 

Podsumowanie i spis 

zagadnień

• Co to jest złożoność i rozróżnienie złożoności 

obliczeniowej oraz czasowej

• Miary złożoności i jej notacje
• Złożoność pesymistyczna, optymistyczna i średnia 

algorytmów prostych

• Złożoność zamortyzowana algorytmów 

sekwencyjnych i zbioru algorytmów 
współpracujących

• Metody wyliczania złożoności
• Sposoby rozwiązywania wybranych typów równań 

rekurencyjnych