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