ALGORYTM
Złożoność obliczeniowa
Pojęcie algorytmu
Algorytm jest ciągiem kroków
obliczeniowych prowadzÄ…cych do
przekształcenia danych wejściowych w
dane wyjściowe.
2
Każdy algorytm:
zðposiada dane wejÅ›ciowe
zðprodukuje pewien wynik
zðjest precyzyjnie zdefiniowany
zðjest skoÅ„czony
Algorytm jest poprawny, gdy dla każdego
zestawu sensownych danych wejściowych
zatrzymuje siÄ™ i daje dobry wynik.
3
Analiza algorytmów
Analiza algorytmów to dział informatyki
zajmujÄ…cy siÄ™ szukaniem najlepszych
algorytmów dla zadań komputerowych.
4
Analiza algorytmów pozwala
odpowiedzieć na pytania:
zðczy dany problem może być rozwiÄ…zany na
komputerze w dostępnym czasie i pamięci
zðktóre ze znanych algorytmów należy
zastosować
zðczy istnieje lepszy algorytm od rozważanego
zðjak uzasadnić, że stosujÄ…c dany algorytm
rozwiąże się zamierzone zadanie
5
DokonujÄ…c analizy algorytmu zwracamy
uwagÄ™ na:
zðjego poprawność semantycznÄ…
zðprostotÄ™
zðczas dziaÅ‚ania
zðilość zajmowanej pamiÄ™ci
zðoptymalność
zðokolicznoÅ›ci, w jakich należy go używać, a w
jakich nie
6
Złożoność obliczeniowa
Złożoność obliczeniową algorytmu definiuje się
jako ilość zasobów komputerowych,
potrzebnych do jego wykonania.
Podstawowymi zasobami sÄ…:
zðczas dziaÅ‚ania (zÅ‚ożoność czasowa)
zðilość zajmowanej pamiÄ™ci (zÅ‚ożoność
pamięciowa)
7
Rozmiar danych
Jednym z decydujących parametrów
mających wpływ na złożoność
obliczeniowÄ… jest rozmiar danych.
Pojęcie rozmiaru danych:
" dla funkcji sortujÄ…cej - rozmiar tablicy
" dla drzewa binarnego - liczba węzłów w drzewie
" dla programu obl.silnię - wielkość danej wejściowej
" dla wielomianu - stopień wielomianu
8
Złożoność pamięciowa
Za jednostkę złożoności pamięciowej
przyjmuje się słowo pamięci maszyny.
9
Złożoność czasowa
zðZÅ‚ożoność czasowa danego algorytmu powinna
nie zależeć od komputera, języka programowania
czy sposobu zakodowania.
zðW tym celu wyróżnia siÄ™ w algorytmie
charakterystyczne dla niego operacje, nazywane
operacjami dominujÄ…cymi.
zðZa jednostkÄ™ zÅ‚ożonoÅ›ci czasowej przyjmuje siÄ™
wykonanie jednej operacji dominujÄ…cej.
10
Operacje dominujÄ…ce
zðAlgorytmy sortowania - porównanie dwóch
elementów lub przestawienie elementów w
ciÄ…gu
zðalgorytmy przeglÄ…dania drzewa binarnego -
przejście dowiązania między węzłami w
drzewie
zðalgorytmy wyznaczania wartoÅ›ci wielomianu -
operacje arytmetyczne +, -, *, /
11
Złożoność obliczeniowa algorytmu
jest funkcjÄ… rozmiaru danych n
Wyróżnia się:
zðzÅ‚ożoność pesymistycznÄ… - ilość zasobów
komputerowych potrzebnych przy  najgorszych
danych wejściowych rozmiaru n
zðzÅ‚ożoność oczekiwanÄ… (Å›rednia) - ilość zasobów
przy  typowych danych wejściowych rozm. n
zðzÅ‚ożoność optymistycznÄ… - ilość zasobów
komputerowych potrzebnych przy  najlepszych
danych wejściowych rozmiaru n
12
Najczęściej rozpatrujemy przypadek
pesymistyczny, gdyż:
zðJest to górna granica możliwego czasu
działania algorytmu
zðdla niektórych algorytmów pesymistyczny
czas działania występuje dosyć często
zðprzypadek  Å›redni jest zbliżony do
pesymistycznego
13
Przykład
Wczytujemy n liczb i drukujemy je w odwrotnej kolejności.
zð Rozmiarem danych, który ma decydujÄ…cy wpÅ‚yw na
długość trwania programu jest liczba elementów do
przetworzenia.
zð NastÄ™puje n razy wykonanie odczytu i n razy wypisanie
na ekranie.
zð Jeżeli wiÄ™c zwiÄ™kszymy liczbÄ™ danych dwukrotnie -
również dwukrotnie wzrośnie czas wykonania programu.
zð Mamy wiÄ™c zależność czasu wykonania programu od
danych jako funkcjÄ™ liniowÄ….
14
Złożoność oznaczamy symbolem O i w nawiasie
umieszczamy typ zależności:
O(n), O(n^2), O(n^3)
zð Przyjmujemy, że wykonanie czynnoÅ›ci czytania lub
wypisania zabiera czas jednostkowy. W takim przypadku
czas wykonania programu będzie oszacowany na n+n czyli
2n. I faktycznie, czas wykonania programu tyle wynosi, i
możemy zapisać, że program wykonuje się w czasie T(2n).
zð Ale nie liczymy czasu wykonania, tylko zÅ‚ożoność
obliczeniowÄ…, a to jest co innego.
zð W przykÅ‚adzie zÅ‚ożoność wynosi O(n).
15
zðW zÅ‚ożonoÅ›ci podamy tylko i wyÅ‚Ä…cznie
rząd wielomianu, czyli jeżeli będzie to 2n,
to O(n), jeżeli 125n to również mamy
złożoność O(n).
zðZÅ‚ożoność mówi nam bowiem najogólniej,
jak szybko będzie rósł czas wykonania
programu przy zwiększaniu rozmiaru
danych wejściowych.
16
zðA co, jeżeli czas wykonania wyniesie
T(n^3+1000n^2+n) ?
zðNajwyższa potÄ™ga wynosi tutaj 3, wiÄ™c
złożoność takiego programu to O(n^3).
17
Jeśli ktoś stwierdzi, że jego program jest
szybki, bo wykonał operację w 10
sekund,
to nie dostaniemy w ten sposób żadnej
konkretnej informacji.
18
Musi on jeszcze odpowiedzieć na następujące
pytania:
zð Jakiego komputera użyÅ‚?
zð Jaka jest czÄ™stotliwość pracy zegara taktujÄ…cego
procesor?
zð Czy program byÅ‚ jedynym wykonujÄ…cym siÄ™ wówczas w
pamięci? Jeśli nie to jaki miał priorytet?
zð Jakiego kompilatora użyto podczas pisania tego
programu?
zð Czy w danym kompilatorze zostaÅ‚y wÅ‚Ä…czone opcje
optymalizacji kodu?
zð itd.
19
zðPotrzebna jest nam miara uniwersalna,
nie mająca nic wspólnego ze szczegółami
natury  sprzętowej .
zðParametrem decydujÄ…cym najczęściej o
czasie wykonania określonego algorytmu
jest rozmiar danych, z którymi ma on
do czynienia.
20
Przykład
var a,liczba,n:integer;
var a,liczba,n,nr:integer;
tab:array[1..100]of integer;
tab:array[1..100]of integer;
begin
begin
write('Podaj szukana liczbe :');
write('Podaj szukana liczbe :');
readln(liczba);
readln(liczba);
write('Podaj ilosc liczb w tablicy :');
write('Podaj ilosc liczb w tablicy :');
readln(n);
readln(n);
a:=1;
nr:=0;
while (a<=n) and (tab[a]<>liczba) do
for a:=1 to n do
a=a+1;
if tab[a]=liczba then nr:=a;
if a<=n then writeln( element o numerze : ', a)
if nr>0 then writeln( element o numerze : ', nr)
else writeln('Nie znaleziono liczby');
else writeln('Nie znaleziono liczby');
readln;
readln;
end.
end.
Złożoność pesymistyczna O(n)
Złożoność średnia O(n/2)
Złożoność O(n)
21