Jadwiga Chudzicka
1
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
2
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
3
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
4
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
5
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
6

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
7
Do najpopularniejszych języków
programowania obiektowego
należą C++, Java, Effel.
Jadwiga Chudzicka
8

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
9

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
10
ZA
OŻONOŚĆ OBLICZENIOWA
ALGORYTMÓW
Jadwiga Chudzicka
11
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
12
ZA
OŻONOŚĆ CZASOWA I
ZA
OŻONOŚĆ PAMI
CIOWA
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.
Jadwiga Chudzicka
13
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
14
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
15

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:
f (d)
"
d " D
D
Terminologia
Jadwiga Chudzicka
16
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
17
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:
"
E[X ] = xi pi
"
i = 1
Jadwiga Chudzicka
18
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
19
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
20
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
21
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
22
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 n0 > 0
oraz c > 0, że:
" 0d" f (n)d" cg(n)
n e" n0
CiÄ…g dalszy
Jadwiga Chudzicka
23
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
24
Graficzny przykład notacji O
cÅ"g(n)
f(n)
f(n)
n
n0
n0
f(n) = O(g(n))
f(n) = O(g(n))
Objaśnienia
Jadwiga Chudzicka
25
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 n0 i c, takie że na
prawo od n0 wartość f(n) jest nie
większa niż cg(n).
Wartość n0 jest minimalną możliwą
wartością; każda większa wartość jest
również dobra.
Jadwiga Chudzicka
26
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 n0 > 0 oraz c > 0, że:
" 0 d" cg(n) d" f (n)
ne" n0
Stosujemy zapis f(n) = ©(g(n)), gdy funkcja f(n)
jest elementem zbioru ©(g(n)).
Jadwiga Chudzicka
27
Graficzny przykÅ‚ad notacji ©:
f(n)
f(n)
cÅ"g(n)
cÅ"g(n)
n
n
n0
n0
f(n) = ©(g(n))
f(n) = ©(g(n))
Objaśnienia
Jadwiga Chudzicka
28
Notacja © daje dolne ograniczenie funkcji z
dokładnością do stałego czynnika. Piszemy f(n)
= ©(g(n)), jeÅ›li istniejÄ… dodatnie staÅ‚e n0 i c,
takie że na prawo od n0 wartość f(n) jest nie
mniejsza niż cg(n).
Wartość n0 jest minimalną możliwą wartością;
każda większa wartość jest również dobra.
Jadwiga Chudzicka
29
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 n0
> 0 oraz c1 > 0 i c2 > 0, że:
" 0 d" c1g(n) d" f (n) d" c2g(n)
ne" n0
dalej
Jadwiga Chudzicka
30
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
31
Graficzny przykład notacji Ś
c2Å"g(n)
c2Å"g(n)
f(n)
f(n)
c1Å"g(n)
c1Å"g(n)
n
n
n0
n0
f(n) = Åš(g(n))
f(n) = Åš(g(n))
Objaśnienia
Jadwiga Chudzicka
32
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 n0 , c1 i c2 , takie że na
prawo od n0 wartość f(n) leży zawsze
między c1g(n) a c2g(n) .
Wartość n0 jest minimalną możliwą
wartością; każda większa wartość jest
również dobra.
Jadwiga Chudzicka
33
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
34
Algorytmy mają zwykle złożoność czasową
proporcjonalnÄ… do funkcji.
Najczęściej spotykane rzędy złożoności algorytmu to:

1 (stała); n3 (sześcienna);


log2n nc (wielomianowa);

(logarytmiczna);
cn (wykładnicza);


n (liniowa);
n! (wykładnicza,
ponieważ n!>2n już

nlog2n (liniowo-
od n=4
logarytmiczna);

n2 (kwadratowa);
Jadwiga Chudzicka
35