Jadwiga Chudzicka

1

Jadwiga Chudzicka

2

KLASYFIKACJA ALGORYTMÓW



algorytmy numeryczne, operujące na liczbach (np. 

algorytm Euklidesa),



algorytmy nienumeryczne, operujące na obiektach 

nieliczbowych (np. sortowanie dokumentów). 

Inny podział to:



algorytmy sekwencyjne (kolejność czynności jest 

jednoznacznie określona),



algorytmy niesekwencyjne (równoległe, w których 

współbieżne następstwo miedzy pewnymi operacjami nie 

jest ściśle określone).

Jadwiga Chudzicka

3

Metody projektowania 

algorytmów



Programowanie strukturalne jest techniką 

programowania, w której problem jest 

dzielony na mniejsze bloki (moduły), 

odpowiedzialne za realizację 

poszczególnych jego części. Dotyczy to 

głównie dużych projektów, które są zbyt 

skomplikowane do opisania w całości. W 

programach komputerowych modułami są 

najczęściej procedury i/lub funkcje. Możliwe 

są przy tym dwa sposoby postępowania: 

Jadwiga Chudzicka

4

W pierwszej metodzie zwanej programowaniem 

zstępującym (ang. top-down programming), 

programista powinien uświadomić sobie, co jest do 

zrobienia i starać się wyodrębnić z całości 

problemu mniejsze zadania. Może je traktować 

tymczasowo jako „czarne skrzynki” o określonych 

właściwościach. To samo należy zrobić z „czarnymi 

skrzynkami”, tzn. próbować wyodrębnić w nich 

jeszcze bardziej szczegółowe zadania. Proces ten 

powinien być kontynuowany tak długo, aż osiągnie 

się poziom szczegółowości implikowany przez 

stosowany język.

Jadwiga Chudzicka

5

W drugiej metodzie zwanej programowaniem 

wstępującym (ang. bottom-up programming), 

najpierw należy zaprogramować elementarne 

struktury, a następnie złożyć z nich program w 

logiczną całość; jest to metoda odwrotna do wyżej 

opisanej.

Jadwiga Chudzicka

6

Do pisania programów z wykorzystaniem 

techniki programowania strukturalnego 

nadają się zwłaszcza strukturalne języki 

programowania, takie jak: 

Pascal

, 

C

, 

Modula-2

. 

Programowanie strukturalne ułatwia 

projektowanie, testowanie a także 

otrzymanie kodu programu.

Jadwiga Chudzicka

7



Programowanie obiektowe – rodzaj 

programowania, w którym dane i wykonywane na 

nich operacje są połączone. Ten formalny zabieg 

umożliwia szybsze pisanie większych programów 

przez „składanie ich” ze wzajemnie powiązanych 

obiektów, które odpowiadają za daną funkcję 

programu (np. przygotowanie danych, wykonanie 

obliczeń, zaprezentowanie wyników). Programując 

obiektowo, należy najpierw „wykryć” wszystkie 

obiekty w rozważanym problemie. Terminem 

obiekt określamy dane i algorytmy na nich 

operujące. Dane w językach programowania 

nazywane są polami obiektu, natomiast algorytmy 

– metodami.

Jadwiga Chudzicka

8

Do najpopularniejszych języków 

programowania obiektowego 

należą 

C++

, 

Java

, 

Effel

.

Jadwiga Chudzicka

9



programowanie dynamiczne – problem 

dzielony jest na kilka zagadnień, ważność każdego 

z nich jest oceniana i po pewnym wnioskowaniu 

wyniki analizy niektórych prostszych zagadnień 

wykorzystuje się do rozwiązania głównego 

problemu, 



metoda zachłanna – nie analizujemy 

podproblemów dokładnie, tylko wybieramy 

najbardziej obiecującą w tym momencie drogę 

rozwiązania, 



programowanie liniowe – oceniamy 

rozwiązanie problemu przez pewną funkcję jakości 

i szukamy jej minimum, 

Jadwiga Chudzicka

10



poszukiwanie i wyliczanie – przeszukujemy 

zbiór danych aż do odnalezienia rozwiązania, 



probabilistyczne rozwiązanie – algorytm 

działa poprawnie z bardzo wysokim 

prawdopodobieństwem, ale wynik nie jest 

pewny, 



heurystyka – człowiek na podstawie swojego 

doświadczenia tworzy algorytm, który działa w 

najbardziej prawdopodobnych warunkach 

(rozwiązanie zawsze jest przybliżone). 

Jadwiga Chudzicka

11

ZŁOŻONOŚĆ OBLICZENIOWA 

ALGORYTMÓW

Jadwiga Chudzicka

12

Jeżeli dany algorytm da się wykonać na maszynie o 

dostępnej mocy obliczeniowej i określonej pojemności 

pamięci oraz w akceptowalnym czasie, to mówi się że 

jest 

obliczalny

. 

Jeżeli algorytm dla coraz większego zbioru danych 

powoduje wzrost czasu obliczeń szybciej niż to 

wynikałoby z funkcji wielomianowej, to mówi się że 

nie jest obliczalny

. 

Wiąże się z tym pojęcie 

złożoności obliczeniowej

 

(pojęcie to wprowadzili J. Hartmanis i R. E. Stearns):

Jadwiga Chudzicka

13

Złożoność obliczeniowa algorytmu – 

ilość zasobów komputera jakiej potrzebuje 

dany algorytm. 

Najczęściej przez zasób rozumie się czas 

oraz pamięć – dlatego też używa się 

określeń 

złożoność czasowa

 i 

złożoność 

pamięciowa

.

ZŁOŻONOŚĆ CZASOWA I 

ZŁOŻONOŚĆ PAMIĘCIOWA

Jadwiga Chudzicka

14

Za jednostkę złożoności pamięciowej przyjmuje 

się pojedyncze słowo maszyny (np. bajt).

W przypadku złożoności czasowej nie można 

podać bezpośrednio jednostki czasu, np. 

milisekundy, ponieważ nie wiadomo na jakiej 

maszynie dany algorytm będzie wykonywany. 

Dlatego też wyróżnia się - charakterystyczną dla 

algorytmu - operację dominującą. Liczba wykonań 

tej operacji jest proporcjonalna do wykonań 

wszystkich operacji.

Jadwiga Chudzicka

15

Rodzaje złożoności czasowej



złożoność pesymistyczna określa 

złożoność w "najgorszym" przypadku. 

Jeśli D oznacza zbiór wszystkich 

możliwych danych wejściowych, d jeden z 

elementów tego zbioru, a f funkcję, która 

dla danego d zwraca liczbę operacji, to 

złożoność pesymistyczna jest 

zdefiniowana jako: 

             sup{f(d): d 

∈

 D}

Jadwiga Chudzicka

16



złożoność oczekiwana określa złożoność 

średnią czyli 

wartość oczekiwaną

 zmiennej 

losowej f. Jeśli wszystkie dane są 

jednakowo prawdopodobne (z 

prawdopodobieństwem niezerowym) wtedy 

wyraża się ona wzorem: 

D

d

f

D

d

∑

∈

)

(

Terminologia

Jadwiga Chudzicka

17

Pojęcie wartości oczekiwanej 

W rachunku prawdopodobieństwa wartość 

oczekiwana (inaczej wartość przeciętna, 

wartość średnia, nadzieja 

matematyczna) zmiennej losowej 

(dyskretnej) jest sumą iloczynów wartości tej 

zmiennej losowej przez prawdopodobieństwa, 

z jakimi te wartości są przyjmowane.

C.D.

 

Jadwiga Chudzicka

18

Pojęcie wartości oczekiwanej c.d.

Formalnie, jeżeli dyskretna zmienna losowa X 

przyjmuje wartości x1, x2, ..., z 

prawdopodobieństwami odpowiednio: p1, p2, ..., 

wówczas wartość oczekiwaną E[X] zmiennej 

losowej X definiujemy jako:

∑

∞

=

=

1

]

[

i

i

i

p

x

X

E

Jadwiga Chudzicka

19

Wykorzystywanie złożoności obliczeniowej do 

badania jakości algorytmu nie zawsze jest 

zalecane, ponieważ operacja dominująca na 

jednym komputerze może wykonywać się 

bezproblemowo i szybko, na innym zaś musi 

być zastąpiona szeregiem instrukcji.

Dlatego też częściej stosuje się złożoność 

asymptotyczną, która mówi o tym jak 

złożoność kształtuje się dla bardzo dużych, 

granicznych rozmiarów danych wejściowych.

Jadwiga Chudzicka

20

Złożoność asymptotyczna

Do opisu złożoności asymptotycznej stosuje się 

trzy notacje:

1. Notacja 

O

 („omikron” lub „Wielkie O”) 

2. Notacja Ω („Wielkie Omega”) 

3. Notacja Θ („Teta”) 
Przedstawimy opis matematyczny tych notacji, 

przyjmując, że dane są funkcje f oraz g, których 

dziedziną

 jest zbiór liczb naturalnych, natomiast 

przeciwdziedziną

 zbiór liczb rzeczywistych 

dodatnich. 

                          Wyjaśnienie terminów

Jadwiga Chudzicka

21

Definicja funkcji

Funkcja matematyczna przekształcająca zbiór X 

w zbiór Y to odwzorowanie (przyporządkowanie), 

które każdemu elementowi zbioru X przypisuje 

dokładnie jeden element zbioru Y.

Zbiór X nazywamy dziedziną funkcji, jego 

elementy argumentami, zaś zbiór Y - 

przeciwdziedziną funkcji. 

Element 

y

 zbioru Y, który jest przypisany danemu 

elementowi x ze zbioru X nazywamy obrazem x, 

albo wartością funkcji dla argumentu x.

Jadwiga Chudzicka

22

Na kolejnych slajdach umieszczone są definicje 

poszczególnych trzech notacji. 

Służą one do opisu czasu działania algorytmu. 

Mówi się wówczas o tzw. rzędzie wielkości 

funkcji.

Jadwiga Chudzicka

23

Ad 1) Notacja 

O

 ("omikron” lub 

"Wielkie O")

Notacja O określa asymptotyczną granicę górną, 

tzn. dla danej funkcji g(n) mówimy, że f jest co 

najwyżej rzędu g, gdy istnieją takie stałe n

0

 > 0 

oraz c > 0, że:

)

(

)

(

0

0

n

cg

n

f

n

n

≤

≤

∀

≥

Ciąg dalszy

Jadwiga Chudzicka

24

Chociaż O(g(n)) jest zbiorem funkcji to 

wygodnie jest stosować zapis f(n) = 

O(g(n)), gdy chcemy wyrazić, że funkcja 

f(n) jest elementem zbioru O(g(n)).

Określenia 

"złożoność co najwyżej O(f(n))"

 

i 

"złożoność O(f(n))"

 są matematycznie 

równoważne.

Jadwiga Chudzicka

25

Graficzny przykład notacji O 

c

⋅

g(n)

n

n

0

f(n)

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

n

0

f(n)

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

Objaśnienia

 

Jadwiga Chudzicka

26

Notacja 

O

 daje górne ograniczenie 

funkcji z dokładnością do stałego 

czynnika. Piszemy 

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

, jeśli 

istnieją dodatnie stałe 

n

0

 

i 

c

, takie że na 

prawo od 

n

0

 

wartość

 f(n) 

jest nie 

większa niż 

cg(n

).

 

Wartość

 n

0

  

jest minimalną możliwą 

wartością; każda większa wartość jest 

również dobra.

Jadwiga Chudzicka

27

Ad 2) Notacja Ω ("Wielkie Omega")

Notacja Ω

 

określa asymptotyczną granicę dolną, tzn. 

dla danej funkcji g(n) mówimy, że f jest co najmniej 

rzędu g, gdy istnieją takie stałe n

0 

> 0 oraz c > 0, że:

)

(

)

(

0

0

n

f

n

cg

n

n

≤

≤

∀

≥

Stosujemy zapis f(n) = Ω(g(n)), gdy funkcja f(n) 

jest elementem zbioru Ω(g(n)).

Jadwiga Chudzicka

28

Graficzny przykład notacji Ω: 

c

⋅

g(n)

n

n

0

f(n)

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

c

⋅

g(n)

n

n

0

f(n)

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

Objaśnienia 

Jadwiga Chudzicka

29

Notacja 

Ω

 daje dolne ograniczenie funkcji z 

dokładnością do stałego czynnika. Piszemy 

f(n) 

= Ω(g(n))

, jeśli istnieją dodatnie stałe 

n

0

 i 

c

, 

takie że na prawo od 

n

0

 

wartość

 f(n) 

jest nie 

mniejsza niż 

cg(n

).

 

Wartość

 n

0

  

jest minimalną możliwą wartością; 

każda większa wartość jest również dobra.

Jadwiga Chudzicka

30

Ad 3) Notacja Θ ("Teta")

Notacja Θ ogranicza funkcję asymptotycznie od góry 

i od dołu tzn. dla danej funkcji g(n) mówimy, że f 

jest dokładnie rzędu g, gdy istnieją takie stałe n

0

 

> 0 oraz c

1

 > 0 i c

2

 > 0, że:

)

(

)

(

)

(

0

2

1

0

n

g

c

n

f

n

g

c

n

n

≤

≤

≤

∀

≥

dalej

Jadwiga Chudzicka

31

Stosujemy zapis f(n) = Θ(g(n)), gdy funkcja 

f(n) jest elementem zbioru Θ(g(n)). 

Można stwierdzić, że f(n) = Θ(g(n)), gdy f(n) 

jest jednocześnie rzędu O(g(n)) i Ω(g(n)).

Wartości wymienionych w tych notacjach stałych: 

c, c1 i c2 wpływają znacznie na efektywność 

algorytmu.

Jadwiga Chudzicka

32

c

1

⋅

g(n)

n

n

0

f(n)

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

c

2

⋅

g(n)

c

1

⋅

g(n)

n

n

0

f(n)

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

c

2

⋅

g(n)

Graficzny przykład notacji Θ 

Objaśnienia 

Jadwiga Chudzicka

33

Za pomocą notacji 

Θ

 szacuje się funkcję 

z dokładnością do stałego czynnika. 

Piszemy 

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

, jeśli istnieją 

dodatnie stałe 

n

0 

, 

c

1

 i c

2 

, takie że na 

prawo od 

n

0

 

wartość

 f(n) 

leży zawsze 

między 

c

1

g(n

) a 

c

2

g(n

) .

 

Wartość

 n

0

  

jest minimalną możliwą 

wartością; każda większa wartość jest 

również dobra.

Jadwiga Chudzicka

34

Posługując się tymi notacjami można określać 

czas działania algorytmów. 

Jeśli np. mówimy, że czas działania algorytmu 

wynosi Ω(g(n)), należy przez to rozumieć, że 

niezależnie od konkretnych danych 

wejściowych o rozmiarze n (dla dostatecznie 

dużych n) czas działania algorytmu dla tych 

danych wynosi co najmniej g(n), pomnożone 

przez pewną stałą. 

Jadwiga Chudzicka

35

Algorytmy mają zwykle złożoność czasową 

proporcjonalną do funkcji. 

Najczęściej spotykane rzędy złożoności algorytmu to:



1 (stała); 



log

2

n 

(logarytmiczna); 



n (liniowa); 



nlog

2

n (liniowo-

logarytmiczna); 



n

2

 (kwadratowa); 



n

3

 (sześcienna); 



n

c

 (wielomianowa); 



c

n

 (wykładnicza); 



n! (wykładnicza, 

ponieważ n!>2

n

 już 

od n=4