1
Temat:
Algorytmy- rodzaje, sposoby przedstawiania, analiza
i ocena złożoności obliczeniowej algorytmów
Pojęcie algorytmu, rola i miejsce algorytmu
w rozwiązywaniu problemu
Struktury danych
Reprezentacja algorytmów:
• Zapis w języku naturalnym- lista kroków
• Schemat blokowy
• Zapis w pseudokodzie
Czas wykonania a złożoność obliczeniowa, notacja O
duże
Analiza złożoności obliczeniowej
algorytmu wyszukiwania sekwencyjnego
2
Rola i miejsce algorytmu w rozwiązywaniu problemu
Algorytm
to sposób (schemat) postępowania prowadzący do
rozwiązania danego, konkretnego problemu. Lub mówiąc inaczej algorytm
to skończony ciąg operacji na obiektach (mogą to być np. liczby, relacje
między liczbami typu a>b, teksty) ze ściśle ustalonym porządkiem
wykonywania, dający możliwość realizacji zadania z określonej klasy.
Algorytm w sensie informatycznym wykorzystuje określone dane o
zdefiniowanych strukturach (np. liczby całkowite, rzeczywiste, zespolone,
tablice jedno i wielowymiarowe) i daje określone wyniki.
Algorytm powinien posiadać cechy:
Poprawność – dla każdego zestawu poprawnych danych wyniki
powinny być poprawne;
Skończony- dla każdego zestawu poprawnych danych algorytm
powinien dawać poprawne wyniki po skończonej liczbie kroków,
Określoność – z algorytmu musi wynikać jednoznacznie jaka ma
być realizowana następna operacja,
Efektywność- algorytm powinien realizować zadanie przy możliwie
najmniejszej liczbie kroków,
Uniwersalność- powinien rozwiązywać nie tylko specyficzne
zadanie ale całą klasę zadań.
Algorytm można zapisać w postaci:
Listy kroków,
Schematu blokowego (flow diagram, flow chart),
Pseudokodu
Wśród algorytmów wyróżnia się:
sekwencyjne – instrukcje wykonywane kolejno, ale mogą
też wystąpić ewentualne rozgałęzienia,
iteracyjne- to algorytmy w których pewne grupy instrukcji są
wykonywane wielokrotnie (ściśle zadaną liczbę razy lub wynikającą z
przebiegu obliczeń),
rekurencyjne- to algorytmy które wywołują same siebie dla
zmieniających się danych
Algorytm powinien posiadać specyfikację gdzie określamy dane z jakich
algorytm korzysta oraz wyniki które powinien dawać, a także niezbędne w
realizacji zmienne pomocnicze.
W algorytmach mogą również występować wyrażenia które są
zbudowane ze zmiennych, stałych, operatorów (np. +, - , *, /) i funkcji
matematycznych. Wyrażenia mogą też przybierać postać wyrażeń
warunkowych. Wówczas do ich budowy wykorzystywane są operatory
relacyjne (np. =, >, <, <=, >=, <>). W algorytmach występują często tzw.
operacje przypisania (np. x:=x +5), określające, że obliczona wartość
wyrażenia z prawej strony zostanie podstawiana pod zmienną ze strony
lewej.
3
Rozwiązanie danego problemu przy zastosowaniu
komputera wymaga realizacji etapów:
Na rysunku pokazano drogę od problemu, który wymaga rozwiązania do
programu komputerowego rozwiązującego problem, przy założeniu, że
potrafimy poprawnie sformułować algorytm. Pętle sugerują, że niektóre
etapy będą powtarzane z powodu różnego rodzaju błędów, których
trudno uniknąć przy bardziej złożonych problemach. Pierwsza grupa
błędów wynika zwykle z błędnych zapisów algorytmu w języku
programowania.
Aby skompilować program (tzn. przetłumaczyć go na ciąg rozkazów w
zapisie zero-jedynkowym zrozumiałym dla komputera) to musi on być
całkowicie zgodny ze standardem danego języka. Ale uzyskanie
programu programu poprawnego językowo nie musi oznaczać, że
poprawnie rozwiązuje problem. Stąd może ponownie wynikać
konieczność zmiany jego wersji źródłowej – co pokazuje większa pętla.
Czasami również będzie konieczność jej rozszerzenia tzn. zmiany
algorytmu.
Program
wynikowy
2. Testowanie –
usuwanie błędów
logicznych
Algorytm
Algorytm
Algorytm
Algorytm
Problem !
Wykonanie programu
Program
źródłowy
Wyniki
Dane
Start
Wprowadź: a
Wprowadź
:
b
Oblicz: P:=a*b
Pisz:”Pole wynosi P=” P
Stop
program pole
var
a, b, p: real;
begin
readln(a);
readln(b);
p:=a*b;
write(’Pole P=
’,p:4:2,’ cm2’)
end.
Kompilacja
1
. Uruchamianie
(usuwanie błędów
jezykowych
4
Przykład sformułowania algorytmu
Zadanie
Sformułuj algorytm obliczający pole prostokąta. Zapisz algorytm w postaci listy
kroków, schematu blokowego i pseudokodu.
a)
Specyfikacja algorytmu:
Dane wejściowe:
a-
pierwszy bok, liczba rzeczywista dodatnia- w cm,
b-
drugi bok, liczba rzeczywista dodatnia- w cm.
Wynik
: P –pole prostokąta (w cm
2
)
Lista kroków:
K1: Wczytaj wartość pierwszego boku do zmiennej a,
K2: Wczytaj wartość drugiego boku i podstaw pod zmienną b,
K3: Oblicz pole i podstaw pod zmienną p
K4: Wyświetl wynik p
b) Pseudokod:
Program pole
{nagłówek}
zmienne
a,b,p: real
{deklaracja zmiennych}
begin
{początek właściwego programu}
czytaj (a)
{wczytanie danych}
czytaj(b)
P:=a*b
{obliczenia}
wyświetl(„Pole wynosi P=”, p)
{wyświetl wynik}
end
{koniec właściwego programu}
c) Schemat blokowy:
d) Zapis w
języku programowania
( np. Pascal)
Start
Wprowadź: a
Wprowadź: b
Oblicz: P:=a*b
Pisz:”Pole wynosi P=” P
Stop
program pole
var
a, b, p: real;
begin
readln(a);
readln(b);
p:=a*b;
write(’Pole P= ’,p:4:2,’ cm2’)
end.
5
Reprezentacja algorytmów
Najbardziej ogólną formą i jednocześnie mało precyzyjną jest opis
słowny w języku naturalnym. Ta forma niesie ryzyko niejednoznaczności
przy złożonych algorytmach. Stosuje się ją dla zasugerowania
rozwiązania.
Popularnym sposobem jest lista kroków postępowania. Kroki
stanowią opis operacji i są zazwyczaj mieszaniną sformułowań
matematycznych i języka naturalnego. Kolejność kroków jest zgodna z
opisem. Wyjątkiem jest operacja przejścia do wskazanego kroku lub też
zakończenia algorytmu.
Przykład:
Problem znalezienia największego wspólnego dzielnika (NWD(n,m) )
dwu liczb całkowitych m i n:
Najbardziej znanym jest algorytm Euklidesa (ok. 300r p.n.e.).
Specyfikacja
Dane: m, n – liczby całkowite, Założenie: n
≥ m
Wynik: NWD(n,m)
Algorytm:
K1. Podziel n przez m. Niech r będzie resztą z dzielenia.
K2. jeśli r=0 to wynikiem jest m. KONIEC.
K3. Wykonaj:
n:=m
m:=r
Przejdz do K1
Przykład: 1 NWD(n=12, m=6)
K1. n/m=12/6= 2 r=0
K2 r=0 . Stąd m=6 jest poszukiwaną liczbą tzn.
NWD(12,6)=6
Przykład: 2 NWD(n=12, m=8)
K1. n/m=12/8= 1 r=4
K2 r≠0 .
K3 n:= 8 m:=4
K1 n/m=8/4=2 r=0
K2 r=0 . Stąd m=4 jest . czyli
NWD(12,8)=4
6
Algorytm NWD(n,m) (powtórzenie):
K1. Podziel n przez m. Niech r będzie resztą z dzielenia.
K2. jeśli r=0 to wynikiem jest liczba
„m”
. KONIEC.
K3. Wykonaj:
n:=m
m:=r i przejdz do K1
Przykład: 3
Określić NWD(n=44, m=16)
K1. n/m=44/16= 2 r=12
K2 r≠0 .
K3 n:= 16 m:=12
K1 n/m=16/12=1 r=4
K2 r≠0 .
K3 n=12 m=4
K1 n/m=3 r=0
K2 r=0 . Stąd m=4 jest .
NWD(44,16)=4
Dowód algorytmu:
Rozważmy zależność:
n
= q*m +r 0 ≤ r < m (*)
gdzie: q- iloraz liczb n i m (liczba całkowita m div n)
r- reszta z dzielenia (n modulo m)
Jeżeli r=0 to każdy dzielnik liczby m jest dzielnikiem n. Zatem największy
dzielnik m (czyli liczba m !) jest dzielnikiem n.
Jeśli r > 0 t z (*) wynika, że każdy wspólny dzielnik liczb „n”, „m” jest
dzielnikiem „r” a także każdy wspólny dzielnik liczb „r”, „m” jest
dzielnikiem „n”. Zatem liczby „n”, „m” oraz „m”, „r” mają te same
wspólne dzielniki – więc też największy z nich jest wspólny. Można więc
parę liczb „n”, „m” zastąpić parą „m”, „r” do jest równoważne: NWD(n,m
)= NWD(m,r ),i co ma miejsce w K3.Ponadto z nierówności 0 ≤ r < m
wynika, że ciąg reszt „r” otrzymywanych w K1 jest ograniczony i malejący,
a ponieważ jego wyrazy są całkowite to po skończonej liczbie kroków
wystąpią równości:
n
= q*m +r r =0
Oznacza to, że w kroku K2 zostanie osiągnięty koniec, a wtedy
NWD(n’,m’.) będzie równy aktualnej wartośći „m’ ”. c.b.d.o.
7
Reprezentacja blokowa algorytmu NWD
Schemat blokowy (sieć działań) składa się z symboli graficznych w
których opisywane są operacje algorytmu.
Stosuje się różne kształty symboli dla rozróżnienia operacji. Następstwo
operacji określają strzałki. Jest doskonałą komunikacją między
„zleceniodawcą” a programistą. Jednak złożone problemy trudno jest
przedstawić przy pomocy tego typu schematów. Dlatego stosuje się różne
poziomy szczegółowości (od ogółu do szczegółu- schemat zstępujący ).
NIE
TAK
START
KONIEC
Wprowadź: n,m
a := n
b:=m
r≠0
n := m
m := r
Wypisz:
NWD(
a,b
)= m
r:= n mod m
Kształty Wejścia/
Wyjścia
Instrukcje
przypisania
Podjęcia decyzji
(sterowanie)
W Wordzie elementy graficzne
występują w zakładce :
Rysuj
Autokształty
Schematy
blokowe
Strzałki blokowe
8
Operacja „MODULO”
Można zdefiniować dodawanie, odejmowanie i inne operacje, tzw.
"modulo". Są one istotne w w teorii algorytmów i metodach szyfrowania.
Niech n mod m oznacza standardową „operację modulo. Z definicji:
n mod m=n-((n div m)*m)
gdzie: div- dzielenie całkowite np. 365 div 7 =52
( a zwykłe dzielenie daje 365/7= 52.14285)
stąd: 365 mod 7 = 365 – 52*7 = 365 – 364= 1
Inny zapis:
m
m
n
n
m
n
−
=
mod
gdzie:
m
n
- podłoga z dzielenia liczb n i m.
Zapis
x
czytamy: Dla dowolnej liczby rzeczywistej x
x
(czytaj: „podłoga
x”- floor ) oznacza największą liczbę całkowitą mniejszą lub równą x.
Zapis
x
(czytamy „sufit x”-ceiling ) oznacza najmniejszą liczbę całkowitą
większą lub równą x. Dla wszystkich liczb rzeczywistych:
1
1
+
<
≤
≤
<
−
x
x
x
x
x
Dla każdej liczby całkowitej n:
n
n
n
=
+
2
2
Dla każdej liczby rzeczywistej n ≥0 i liczb całkowitych a,b ≥0:
ab
n
b
a
n
=
/
(
)
(
)
b
b
a
b
a
/
1
−
−
≥
Powyższe relacje zachodzą dla funkcji sufit (ale znak relacji odwrotny!!)
Dzielenie modulo
Dzielenie modulo zwraca resztę z dzielenia. Tzn jeżeli dzielimy 2 liczby
całkowite (tylko na takich liczbach operacja ta jest dozwolona) to często
wynikiem jest ułamek. np wynik dzielenia 3/2 będzie 1 (jeżeli wynik ma być
typu
int
) żeby określić jaka liczba jest po przecinku stosujemy dzielenie
modulo. Wynik dzielenia też jest zawsze typu
int
Jeżeli wynikiem dzielenia jest liczba całkowita np: 4/2=2, to wynikiem
dzielenia modulo jest 0 (4 %2=0). W ten sposób bada się parzystość
liczby.
Przykłady operacji modulo .
16 mod 16 = 0 10 mod 16 = 10 17 mod 16= 1 20 mod 16 = 4
9
Reprezentacja algorytmu NWD w pseudokodzie
Formą opisu algorytmów jest tzw. pseudokod (pseudojęzyk), zbliżony do
języka wysokiego poziomu np. Pascala lub C. Pseudojęzyk nie uwzględnia
technik programowania np. stosuje abstrakcyjne typy danych zamiast
standardowych, pomija obsługę błędów i deklaracje zmiennych lokalnych.
Dopuszcza nieformalne opisy zmiennych i parametrów, korzysta też
z języka naturalnego i symboliki matematycznej. Ma to na celu
uproszczenie opisu algorytmu i zrozumienie logiki działania a
jednocześnie zachowanie specyfiki języka, co ułatwia implementację. Oto
opis algorytmu NWD(n,m):
function
EUCLID(n,m)
r:= n
mod
m
while
r≠0
do
n:= m
m:= r
r:= n
mod
m
return
m
Inna forma zapisu:
function
EUCLID(n,m)
r:= n
mod
m
while
r≠0
do
begin
n:= m
m:= r
r:= n
mod
m
end
return
m
Nagłówek określa nazwę algorytmu i jego parametry (n,m). Oba parametry
są przekazywane przez wartość . tzn, że otrzymują one wartości, których
zmiany wewnątrz programu będą poza nim niewidoczne. Instrukcja
„return” poza zakresem „while” kończy algorytm. Jako wynik zwracana
jest wartość m.
while
r≠0
do
- powtarzaj to co
poniżej dopóki r jest różne od
zera
Zwróć jako wynik aktualną
wartość m
Inne- zaznaczenie bloku
powtarzalnych instrukcji
obramowane jak w Pascalu
begin
....
end-
lub też jak w C++
{
.........
}
10
Metody konstruowania algorytmów
Prawie każdy problem można zakwalifikować do jakiejś klasy, dla
której znane są algorytmy rozwiązania. Gdy nie ma gotowego rozwiązania
to przydatne mogą być metody tworzenia algorytmów:
• metoda „dziel i zwyciężaj”
• programowanie dynamiczne,
• metoda zachłanna
• metoda prób i błędów
Każdy z algorytmów, niezależnie od metody którą stosuje, korzysta z kolei
z pewnych technik realizacyjnych. Z tego punktu widzenia możemy
wyróżnić rozwiązania :
• iteracyjne- obliczenia są wykonywane sekwencyjnie w pętlach
bazujących na instrukcjach np. „while” i „for”,
• rekurencyjne – program realizujący, wielokrotnie wywołuje sam
siebie siebie. Ta skomplikowana technika jest możliwa dzięki
mechanizmowi stosu.
Metoda „dziel i zwyciężaj” (
divide and conquer
)- jej najprostsze
zastosowanie i wyjaśnienie to tzw. wyszukiwanie binarne. Polega on na
stwierdzeniu czy liczba „x” występuje w pewnym ciągu liczb (tzw. kluczy)
rosnąco uporządkowanych. Naturalnym opisem problemów
rozwiązywanych metodą „dziel i zwyciężaj” jest stosowanie rekurencji.
Najbardziej znanym rozwiązaniem wykorzystującym „dziel i zwyciężaj” jest
najszybszy znany aktualnie algorytm sortowania QuickSort.
Programowania dynamiczne również stosuje podział na podproblemy
i metodą wstępującą dochodzi do rozwiązania. Przykładem jest tzw. ciąg
Fibonacciego stosowany w opisie zjawisk przyrodniczych i informatyce.
Metoda zachłanna
( greedy algorithms)
- może być przedstawiona w
postaci np. problemu wydawania reszty po dokonaniu zakupów. Wydaje
się resztę zaczynając od największych nominałów i ich krotności. Jest
stosowana również w problemie wyznaczenia najkrótszych dróg (połączeń)
w sieci.
Metoda „prób i błędów” jest stosowana gdy nie można wyrażenie określić
reguły obliczeniowej. W kolejnych krokach dokonuje się wyborów
poprawiając rozwiązanie. Niekiedy trzeba tu dokonywać „nawrotów”.
Przykładem jest tzw. problem plecakowy, który może być interpretowany
np. jako upakowanie kontenerów w ładowni statku.
Dla podanych metod są stosowane zarówno wersje iteracyjne
i rekurencyjne algorytmów.
11
Algorytmy iteracyjne- reprezentacja w języku programowania
Algorytmy iteracyjne cechuje wielokrotna powtarzalność pewnych
obliczeń, realizowana zwykle z wykorzystaniem pętli. Np. w przypadku
algorytmu obliczania silni ( n! ) sposób obliczania można zapisać
następująco:
O!=1
1!=1
2!=1*2
3!=1*2*3
…………….
n! = 1*2*3* … *j*…*(n-2)*(n-1)*n
Z definicji wynika, że obliczenie silni dla wartości n wymaga mnożenia
przez siebie wszystkich kolejnych liczb naturalnych. Operacją podstawową
jest mnożenie kolejnej liczby „j” przez wartość s, która jest
dotychczasowym iloczynem liczb 1,2,3,…,(j-1). Czyli
n! = s * j*…*(n-2)*(n-1)*n
Ta operacja jest tu powtarzalną a jej liczba powtórzeń jest z góry
określona. W implementacji programowej można zastosować tzw. pętlę
for. Jej najprostsza struktura w pseudokodzie jest następująca:
for j= Liczba_początkowa :krok: Liczba_koncowa do
begin instrukcje powtarzane w pętli end
W przypadku obliczania silni pętla przyjmie postać:
for j= 1 : 1 : n do
lub prościej
for j= 1: n do
begin
s := s *j
end
Ponieważ nowa wartość iloczynu s jest wartością poprzednią mnożoną
przez bieżącą wartość j -to na początku wartość s musi być ustawiona tak,
aby była niezmienniczą względem mnożenia tzn. s=1.
W języku Matlab skrypt (czyli ciąg instrukcji) obliczający wartość
silnia(n) można zapisać:
% SKRYPT OBLICZA WART.
n=input
(‘Podaj n=’
);
if
n>0
s=1;
for
j=1:n
s=s*j;
end
sprintf
(‘%d != d%’
,n,s)
elseif
n==0
disp
(‘0! = 1’
);
else
disp(
‘Silnia nie istnieje’
);
end
Okno edytora Matlaba i okno Command uruchamiania skryptu
Silnia_ITERACYJNIE.m
wraz z wynikiem obliczeń dla n=8
12
Algorytmy rekurencyjne- reprezentacja w języku programowania
Obliczanie silni dla liczby całkowitej n>0 jest też definiowane wzorem
nazywanym wzorem (algorytmem) rekurencyjnym:
n! = (n-1)*n
Zaletą takiego definiowania jest krótki zapis, ale sama realizacja jest
złożona.
Aby wykorzystać wzór rekurencyjny trzeba go zaprogramować w postaci
tzw. funkcji.
Funkcja rekurencyjna- to funkcja która wywołuje sama siebie.
W Matlabie funkcja zaczyna się słowem kluczowym function, oraz być
zapisana w pliku o nazwie zgodnej z nazwą funkcji (to wymaga by plik miał
nazwę silnia.m). Ostatnia z wykonywanych instrukcji funkcji musi zapewnić
podstawienie wartości - w tym przypadku musi to być nadanie wartości
zmiennej s. Parametr w nawiasie (tu n) jest przekazany z zewnątrz (z
miejsca wywołania) przez tzw. wartość.
function
s = silnia(n)
sprintf(
'Wchodzę z n=%d'
,n);
disp(ans);
if
n==0
s=1;
else
s=n * silnia(n-1);
end
Śledzenie rekurencji w obliczaniu silni przy pomocy powyższej funkcji:
>> silnia(6)
% przykładowe uruchamienie funkcji z konsoli
Wchodzę z n=6
Wchodzę z n=5
Wchodzę z n=4
Wchodzę z n=3
Wchodzę z n=2
Wchodzę z n=1
Wchodzę z n=0
720
>>
W przypadku wywołania w postaci s= silnia(6) wynik jest w zmiennej s.
To oznacza (5!)*6- czyli trzeba obliczyc 5! –
rekur.: Silnia(5)
To oznacza (4!)*5*6 itd
13
Czas wykonania programu a złożoność obliczeniowa.
Niech będzie dany pewien algorytm A o którym przyjmiemy założenia:
• czas wykonania operacji elementarnej wynosi 1µs,
• czas wykonania algorytmu (liczba operacji) jest proporcjonalny do
pewnej funkcji matematycznej
W tabeli przedstawiono czasy wykonania programów dla algorytmów
różnej klasy.
Rozmiar danych (wartość n w algorytmie)
Klasa
algorytmu
10
20
30
40
50
n
0,000 01s 0,000 02s 0,000 03s 0,000 04
0,000 05
n
2
0,000 1s
0,000 4s
0,000 09s 0,001 6s
0,002 5s
n
3
0,001s
0,008s
0,027s
0,064s
0,125s
2
n
0,001s
1,0s
17,9min
12,7dni
35,7
lat
3
n
0,59s
58min
6,5
lat
3855
wieków
2*10
6
wieków
n
!
3,6s
756
wieków
8,4*10
6
wieków
9,6*10
48
wieków
2,6*10
66
wieków
Algorytmy ocenia się na podstawie różnych kryteriów zależnych od
okoliczności ich stosowania. Zazwyczaj istotna jest prostota i „elegancja”,
czas działania, dokładność obliczeń (dla algorytmów numerycznych).
Często wybór algorytmu jest kompromisem między np. prostotą a
efektywnością. Algorytmy prostsze są łatwiejsze do zrozumienia,
implementacji programowej i testowania, ale zwykle ich czas realizacji jest
dłuższy. Bardziej efektywne algorytmy są zwykle bardziej skomplikowane.
Wymagają stosowania bardziej złożonych technik programowania np.
rekurencji.
Podstawowymi zasobami każdego algorytmu są :
czas wykonania,
wielkość zajmowanej pamięci
.
Analiza algorytmu polega na określeniu niezbędnych zasobów do jego
wykonania. Należy uwzględnić też jego poprawność, prostotę i
użyteczność praktyczną. Analiza kilku algorytmów dla danego problemu
pozwala zwykle na wybór najlepszego pod względem czasu jak i pamięci.
Wielkość zasobów komputerowych potrzebnych do wykonania
algorytmu określa się mianem
złożoności obliczeniowej.
Dla wielu
algorytmów czas ich wykonania i wielkość pamięci powiększa się gdy
14
wzrasta wielkość zestawu danych. Dlatego często złożoność obliczeniowa
traktowana jest jako funkcja zależna od rozmiaru danych wejściowych,
nazywanego rozmiarem problemu lub zadania, który jest liczbą całkowitą
wyrażającą wielkość zestawu danych. Na przykład w problemie
sortowania za rozmiar problemu przyjmuje się liczbę elementów ciągu
wejściowego, a przy wyznaczaniu wyznacznika macierzy- liczbę wierszy
i kolumn.
Pozostaje
jeszcze
kwestia
określania
jednostki
złożoności
obliczeniowej. W przypadku złożoności pamięciowej za jednostkę
przyjmuje się komórkę pamięci.
W zależności od kontekstu może to być bajt lub inna jednostka pamięci
zajmowanej przez wartość typu prostego. Np. dla algorytmów działających
na zmiennych typu real, jest to zwykle 8 bajtów.
W przypadku złożoności czasowej w algorytmie wyróżnia się
charakterystyczne operacje o tej własności, że całość wykonanej przez
algorytm pracy jest proporcjonalna do liczby tych operacji. Są to operacje
dominujące. Np. w algorytmie sortowania liczb taką operacją jest
porównanie dwu elementów ciągu wejściowego i ich ewentualne
przestawienie, a w algorytmach obliczania wyznacznika macierzy-
operacje arytmetyczne +,*,- /.
Jednostką miary złożoności czasowej jest wykonanie jednej operacji
dominującej.
Zaletą tak zdefiniowanej złożoności czasowej jest jej uniwersalność
i niezależność od:
szybkości procesora,
cech języka programowania i umiejętności programisty.
Złożoność czasowa staje się miarą jego efektywności czasowej, a
własności algorytmu zależą tylko od niego i rozmiaru danych.
W rzeczywistości nie jest zupełnie prawdą ponieważ czas wykonania
algorytmu np. sortowania może się różnić dla danych o tym samym
rozmiarze. Np. w posortowanym ciągu wejściowym nie wystąpią
przestawienia elementów, a gdy jest odwrotnie posortowany liczba
przestawień jest największa. Stąd czasami bierze się pod uwagę tylko
operacje porównania.
Do oceny złożoności czasowej algorytmów wykorzystuje się pewne
notacje, które mówią jak wygląda ta złożoność obliczeniowa jeśli liczba
danych „n” rośnie.
Najczęściej stosowaną jest notacja O duże
. Celem
stosowania tej notacji jest pokazanie charakteru wzrostu złożoności
obliczeniowej (np. liniowa, kwadratowa, logarytmiczna).
15
Oto przykłady najważniejszych rodzajów złożoności algorytmów
n
Rodzaj złożoności
Przykład
O(1)
Stała
Dostęp do elementu tablicy
O(logn)
logarytmiczna
Przeszukiwanie binarne
0(n)
liniowa
Przeszukiwanie
sekwencyjne
O(nlogn)
Liniowo-logarytmiczna
Sortowanie kopcowe
0(n
2
)
kwadratowa
Sortowanie bąbelkowe
O(n
3
)
sześcienna
Mnożenie macierzy
O(2
n
)
wykładnicza
Algorytm plecakowy
Wieże Hanoi
O(n
!
)
wykładnicza
Generowanie permutacji
Gdzie:
O(…) tzw notacja O duże określająca złożoność obliczeniową algorytmu
Jest oczywistym, że złożoność obliczeniowa przekłada się na czas
obliczeń na konkretnej platformie sprzętowej (komputerze).
16
Analiza złożoności algorytmu przeszukiwania sekwencyjnego
Problem przeszukiwania określony jest też jako wyszukiwania. Jego
specyfikacja jest następująca:
Dane:
x
element
i
a
tablicy
w
a
a
a
liczb
n
Ciąi
n
[]
,
,
,
2
1
K
Wynik:
Indeks „k” taki, że x=a
k
lub –1, gdy x nie ma w ciągu
Najprostszy algorytm zwany jest przeszukiwaniem sekwencyjnym
(sequential search), polega na przeglądaniu kolejnych elementów ciągu i
kończy się, gdy poszukiwany element zostanie znaleziony lub cały ciąg
zostanie przeszukany. Algorytm można zapisać następująco:
Function SEQUENTIAL-SEARCH(a[1..n],x)
1
for k:=1 to n do
2
if x=a[k] then
3
return k
4
return –1
Można powiedzieć złożoność algorytmu zależy gdzie w tablicy znajduje
się szukany element” – jeśli w ogóle jest!
Operacjami dominującymi w algorytmie są porównania. Ich liczba jest
równa liczbie wykonań pętli for. Najlepszy przypadek jest jeśli x jest
pierwszym elementem ciągu, a najgorszy gdy ostatnim lub nie występuje.
Zatem:
W(n)=T(n)=n -(przypadek Worst)
B(n) =T(1)=1 (przypadek Best)
Stosując notację O duże:
T(n)=W(n)=O(n)
W ocenie algorytmów bardziej istotne są oceny pesymistyczne,
czyli najdłuższe czasy działania dla dowolnych danych rozmiaru
n z powodu, że:
• Algorytm nie będzie działał dłużej,
• Przypadek pesymistyczny jest częsty np. brak inf. w bazie,
Przypadek „średni” - często zbliżony do pesymistycznego
W każdym obiegu pętli
for
sprawdza się czy element
tablicy jest równy
szukanemu elementowi
x
(wiersz2) . Jeśli tak jest
zwracana jest wartość
in
deksu
k
(wiersz 3)
17
Dalej przedstawiono analizę przypadku średniego. Założymy że
prawdopodobieństwo zdarzenia , że
x
występuje w ciągu wynosi
p
, oraz
że jeśli w nim występuje to prawdopodobieństwo zdarzenia, że występuje
na pozycji
k
wynosi
p/n
, a prawdopodo-bieństwo zdarzenia, że nie
występuje w ciągu wynosi
(1-p)
.
Zatem p-stwo
p
k
zdarzenia
ω
k,
że algorytm wykona
k
porównań przy
poszukiwaniu wartości
x
wynosi:
)
(
)
1
(
1
,
,
2
,
1
(
n
k
p
n
p
n
k
n
p
p
k
=
−
+
−
=
=
K
Przypadek
k=n
oznacza:
• Element x jest na pozycji n (ostatniej),
• Lub element x nie występuje, ale żeby to stwierdzić trzeba przejrzeć
wszystkie elementy od 1 do n.
Stąd pk dla k=n jest sumą zdarzeń.
Niech
X
n
oznacza zmienną losową, której wartościami są liczby porównań
wykonywanych przez algorytm dla danych rozmiaru
n:
( )
)
,
,
2
,
1
(
n
k
k
X
k
n
K
=
=
ω
Jej wartość oczekiwana wynosi:
( )
( )
(
)
(
)
(
) ( )
2
2
1
1
2
1
1
1
1
1
1
p
p
n
p
n
n
n
n
p
p
n
k
n
p
p
n
n
p
k
p
X
X
E
n
k
n
k
n
k
k
k
n
n
+
−
=
−
+
+
=
=
−
+
=
−
+
=
=
∑
∑
∑
=
=
=
ω
Ostatecznie średnia A(n) (Average) liczba porównań w algorytmie przy
założeniu, że p-stwo wystąpienia poszukiwanego elementu wynosi
p
, jest
określona zależnością:
( )
( )
2
2
1
p
p
n
X
E
n
A
n
+
−
=
=
Na podstawie tej zależności rozpatrzmy przypadki:
Jeśli
p=1,
tzn.
x
na pewno występuje - to
A(n)=(n+1)/2
. Czyli
średnio przeszukuje się połowę ciągu,
Jeśli
p=1/2
, to
A(n)=(3n+1)/4
Czyli średnio przeszukuje się 3/4
elementów ciągu,
Jeśli
p jest bliskie zera
to
A(n)
jest bliski
n.
Czyli średnio trzeba
przeszukać cały ciąg.
X –nie wystąpi w ciągu
Ale taka suma =n(n+1)/2
18
Przeszukiwanie binarne- Zastosowanie metody
„dziel i zwyciężaj”. Złożoność obliczeniowa algorytmu
Specyfika przeszukiwania binarnego jest następująca:
Dane:
x
element
szukany
i
a
a
a
liczb
n
Ciąi
n
,
,
,
2
1
K
O ciągu zakładamy, że jego elementy są uporządkowane niemalejąco.
Wynik:
Indeks „k” taki, że x=a
k
lub –1, gdy x nie ma w ciągu
Można zastosować algorytm przeszukania binarnego (binary search),
który jest znacznie efektywniejszy niż sekwencyjny.
Algorytm jest oparty na metodzie
„dziel i zwyciężaj”.
Załóżmy początkowo, że w rozpatrywanym ciągu
i=1, j=n.
j
i
i
i
a
a
a
a
,
,
,
2
1
K
+
+
Dla jego środkowego elementu o indeksie k=(i+j)/2 wystąpi jeden z
trzech przypadków:
x=a[k] –
element
x
został znaleziony na pozycji
k
, należy więc
zakończyć algorytm,
x<a[k] -
element
x
może wystąpić tylko w lewej połowie, więc należy
ją rozpatrzyć przyjmując
j=k-1
,
x>a[k] -
element x może wystąpić tylko w prawej połowie, , więc
należy ją rozpatrzyć przyjmując
i=k+1
,
Jeśli po wykonaniu kolejnego kroku zachodzi nierówność
i >j
, to
poszukiwanie kończy się niepomyślnie, a jego wynikiem jest
–1
.
Function
BINARY-SEARCH(a[1..n])
i:=1,
j:=1
while
i ≤ j
do
k:= (i +j)
div
2
if
x= a [k]
then
return
k
else
if
x < a [k]
then
j := k-1
else
i := k +1
return
–1
To jest wersja
iteracyjna
algorytmu
wyszukiwania
19
Złożoność czasową można wyrazić jako liczbę wykonań pętli
while
w
zależności od
n.
W każdym wykonaniu mają miejsce w zasadzie dwa
porównania. Można traktować jako operację i przyjąć że w każdej pętli
jest jedna operacja dominująca.
Czyli dla n=1 wykonywana jest jedna operacja dominująca, zaś dla n >1
problem jest redukowany do problemu 2-razy mniejszego, gdy wykonanie
operacji dominującej nie kończy się sukcesem- czyli gdy poszukiwany
element nie jest środkowym w ciągu. Złożoność czasową można tu
wyrazić w postaci zapisu z rekurencją (analiza opiera się na intuicji):
( )
)
1
(
1
2
)
1
(
1
>
+
=
=
n
n
T
n
n
T
(1)
Metodą indukcji można pokazać, że dla dowolnych n
zachodzi wzór:
( )
1
log
2
+
=
n
n
T
(7)
Zazwyczaj uważa się, że jeden algorytm jest lepszy od drugiego,
jeśli jego złożoność obliczeniowa jest funkcją niższego rzędu względem
rozmiaru danych. W przypadku przeszukiwania sekwencyjnego jest nią
funkcja liniowa a w przypadku binarnego funkcja logarytmiczna. Zatem
lepszym powinien być algorytm przeszukiwania binarnego
.
Tab. Porównanie złożoności czasowej algorytmów
przeszukiwania ciągów
n
Sekwencyjne
binarne
10
10
4
100
100
7
1000
1000
10
10 000
10 000
14
100 000
100 000
17
1 000 000
1 000 000
20
20
Przeszukiwanie binarne. Przykład.
Niech będzie dany ciąg 12 liczb przedstawiony w tabeli.
Poszukujemy liczby x=18.
0
1
2
3
4
5
6
7
8
9
10
11
1
2
6
18
20
23
29
32
34
39
40
41
Left=0 right=11 mid=( Left + right)/2=5
Tab[mid]=23
18<23 18=23 18>23
1
2
6
18
20
23
29
32
34
39
40
41
Left=0 right=mid=4 mid=( Left + right)/2=2
Tab[mid]=6
18<6 18=6 18>6
1
2
6
18
20
23
29
Left=mid=2 right=4 mid=( Left +
right)/2=3
Tab[mid]=18
18<18 18=18 18>18
gdzie:
left- lewy indeks przeszukiwanej części tablicy wejściowej,
right- prawy lewy indeks przeszukiwanej części tablicy,
mid- indeks elementu środkowego analizowanego aktualnie
fragmentu tablicy
Poszukiwanie kończy się pomyślnie po 3 etapach.
21
Poszukiwanie binarne. Metoda iteracyjna i rekurencyjna –
porównanie algorytmów.
Algorytm iteracyjny ma postać:
Function
BINARY-SEARCH(a[1..n], x)
i:=1
j:=n
while
i ≤ j
do
k:= (i +j)
div
2
if
x= a [k]
then
return
k
else
if
x < a [k]
then
j := k-1
else
i := k +1
return
–1
Algorytm rekurencyjny można przedstawić w postać:
function
BINARY-SEARCH2(a[1..n], x, i, j)
if i>j then
return –1
k:=(i + j) div 2
if x = a[k] then
return k
else if x < a[k] then
return
BINARY-SEARCH2
(a, x, i, k-1 )
else
return
BINARY-SEARCH2
(a, x, k+1, j )
Sprawdzenie czy element x znajduje się w tablicy a[1..n] polega na
wywołaniu:
BINARY-SEARCH2
(a, x, 1, n )
To jest wersja
iteracyjna
algorytmu
poszukiwania
22
Aby bardziej upodobnić nagłówek do wersji iteracyjnej można pozbyć się
dwu ostatnich parametrów (tzn i, j), ukrywając rekurencję przez
wyodrębnienie wewnętrznej funkcji poszukującej SEARCH.
function
BINARY-SEARCH3(a[1..n], x)
function SEARCH(i, j)
if i>j then
return –1
k:=(i + j) div 2
if x = a[k] then
return k
else if x < a[k] then
return SEARCH(i, k - 1)
else
return SEARCH(k+1, j)
return SEARCH(1, n)
Jedyną instrukcją BINARY-SEARCH3 jest return SEARCH(1,n),
która uaktywnia funkcję SEARCH(i,j)