Wykład I
1. Pojęcie algorytmu
Definicja nieformalna
Algorytmem jest pewna ściśle określona procedura obliczeniowa, która dla właściwych
danych wejściowych  produkuje żądane dane wyjściowe zwane wynikiem działania
algorytmu.
Dane Dane
Algorytm
wejściowe wyjściowe
Inne definicje:
Algorytm to
- ciąg kroków obliczeniowych prowadzących do przekształcania danych wejściowych w
dane wyjściowe;
- skończony ciąg reguł, które aplikuje się na skończonej liczbie danych, pozwalający
rozwiązywać zbliżone do siebie klasy problemów;
- zespół reguł charakterystyczny dla pewnych obliczeń lub czynności.
y
ródłosłów:
Perski pisarz  matematyk Abu Jafar Mohammed ibn Musa al-Khowarizmi
( IXw n.e.)
- podał regułę wyjaśniającą krok po kroku zasady operacji arytmetycznych na liczbach
dziesiętnych;
- po Å‚acinie jego nazwisko brzmi: Algorismus.
Słowo algorytm często jest również kojarzone z greckim matematykiem Euklidesem (365-
300 p.n.e.), który przedstawił m.in. sformalizowane algorytmy:
" dzielenia kąta na połowy;
" badania identyczności dwóch kątów;
" obliczania Największego Wspólnego Podzielnika tzw. NWP dwóch liczb
naturalnych.
Algorytmy stworzone przez Euklidesa wykorzystywały w swoich działaniach elementarne
operacje, które mogły być wykonane w sposób jednoznaczny, tzn.
- dla algorytmów geometrycznych były to operacje typu prosta  okrąg, wykonywane
przy pomocy cyrkla i linijki;
- dla algorytmów obliczeniowych (numerycznych) były to operacje arytmetyczne: +, -, *, /
oraz porównywania.
Nas interesować będą algorytmy w kontekście informatycznym, tzn. przekształcające
efektywnie dane wejściowe na dane wyjściowe zwane również wynikiem.
Cechy algorytmu informatycznego:
posiada dane wejściowe, które pochodzą z dokładnie określonego zbioru, np. ze
zbioru liczb naturalnych N, ze zbioru liczb rzeczywistych R;
produkuje pewien wynik (niekoniecznie numeryczny);
jest precyzyjnie zdefiniowany, tzn. każdy jego krok jest jednoznacznie określony i
obejmuje wyłącznie operacje elementarne;
jest skończony, tzn. w skończonym czasie wyprodukuje wynik, a czas jego działania
powinien być możliwie precyzyjnie określony;
jest jednoznaczny ( inaczej powtarzalny), tzn. jego wielokrotne wykonywanie dla
identycznych danych wejściowych daje zawsze taki sam wynik;
jest kompletny, tzn. uwzględnia wszystkie możliwe przy-padki, jakie mogą wystąpić
podczas jego wykonywania;
jest uniwersalny, tzn. umożliwia rozwiązanie całej klasy zadań, a nie tylko
pojedynczego, ustalonego zadania.
Formy przedstawiania algorytmu informatycznego
opis słowny, zazwyczaj z formułami matematycznymi
schemat graficzny
" schematy blokowe czyli ciÄ…gi znormalizowanych symboli graficznych
połączonych skierowanymi liniami
" strukturogramy czyli graficzne schematy zwarte
specjalne języki matematyczne zwane pseudokodami
języki programowania wyższego poziomu np. PASCAL, Fortran, C, BASIC, ADA,
Simula, itp.
Schematy blokowy  lista bloków
Tzw. schematy Bohma  Jacopiniego.
Blok
poczÄ…tek
wprowadzić a,b,c
WE
poczÄ…tk
Blok
pisz
 Brak danych
końca W4
koniec
Tak
x=xÅ"y Blok
Blok decyzyjny
warunek
operacy
Nie
Bloki
Blok
Å‚Ä…cznikowe
dla i=1 do n
1
iteracyj
2
Bloki iteracyjne
Powtarzaj Dopóki
dopóki wykonuj
Ciąg czynności
Nie
warunek
Tak
Nie
warunek
Ciąg czynności
Tak
Strukturogramy zwarte
(Diagramy Nassi - Shnaeidermana)
Blok wejścia (klawiatura, plik)
A
Blok wyjścia (monitor, drukarka, plik)
A
Blok operacyjny
Operacja
Warunek Blok decyzyjny
tak nie
Blok 1 Blok 2
wyrażenie Blok wyboru z szeregu możliwości
W1
Blok 1 W2
Blok 2 W3 Inaczej
Blok 3 Blok
i=1,m Pętla - cykliczne wykonanie bloku dla 1,...,m
Blok - treść pętli
warunek pętla typu
dopóki wykonuj
blok
pętla typu
blok powtarzaj aż do
warunek
nazwa algorytmu blok procedury
(odrębnego, nazwanego fragmentu algorytmu)
Typy algorytmów
Z punktu widzenia organizacji wykonywanych czynności (obliczenia, rysowanie,
porównywanie) rozróżniamy trzy podstawowe typy algorytmów:
liniowy (sekwencyjny): wszystkie czynności są wykonywane w ściśle określonej
kolejności, jedna za drugą;
z rozgałęzieniami (selekcja): kolejność i zakres wykonywanych czynności zależy od
warunków, których spełnienie (lub niespełnienie) zależy od danych wejściowych oraz
pewnych wyników pośrednich;
iteracyjny (pętla): pewien ciąg identycznych czynności (tzw. cykl lub pętla) jest
powtarzalny wielokrotnie dla różnych danych.
Przykłady różnych form przedstawienia algorytmu.
Opis słowny
Problem: Oblicz wartość funkcji:
x
f(x) =
x
Dane : dowolna liczba rzeczywista x"R
Wynik: wartość funkcji f(x) określona jest wzorem:
-1 dla x<0
f(x)= 0 dla x=0
1 dla x>0
Algorytm:
krok 0: Podaj wartość danej x
krok 1: Jeśli x>0, to f(x)=1.
Zakończ algorytm
krok2: Jeśli x=0, to f(x)=0 {Dla x <= 0}
Zakończ algorytm
krok 3: Mamy f(x)=-1. { < 0
Dla x }
Zakończ algorytm
Schemat blokowy
poczÄ…tek
podaj x
TAK
NIE
x<0
TAK NIE
x=0
wynik=-1
wynik =
wynik = 0 wynik = 1
koniec
Koniec
koniec koniec
Zapis w pseudokodzie :
Funkcja f(x)
poczÄ…tek
wczytanie x
jeżeli x>0 to pisz f(x)=1
w przeciwnym razie
jeżeli x=0 to pisz f(x)=0
w przeciwnym razie pisz f(x)= -1
koniec
Program w języku Turbo Pascal
PROGRAM funkcja;
VAR x: Real;
BEGIN
READ (x);
IF x>0 THEN WRITE(1)
ELSE IF x=0 THEN WRITE(0)
ELSE WRITE(-1);
END.
Kilka faktów z historii algorytmiki
W rozwoju algorytmiki można wskazać kilka istotnych dat oraz osób, które są ważnymi
punktami zwrotnymi:
1801 - Francuz Joseph Marie Jacquard
- konstrukcja krosna tkackiego  programowanego przez kartÄ™ perforowanÄ…
1833 - Anglik Charles Babbage
- konstrukcja maszyny do wyliczania pewnych formuł matematycznych
1890 - Amerykanin Herman Hollerith
- maszyna do opracowywania danych statystycznych (spisy ludności)
1911  powstała IBM
1930 - badania teoretyczne
Allan Turing, Carl GQ
del, Markov
1940 - pierwsze maszyny liczÄ…ce: MARK1, ENIAC
EDVAC: pierwszyy prawdziwy komputer
- koncepcja Johannesa von Neumanna
program jako dane w pamięci komputera
lata 60-te - pierwsze duże systemy informatyczne (COBOL, ALGOL)
- początki metodologii: intuicja, wyczucie prowadziły do wielu błędów, małej
wiarygodności; potrzebne były duże nakłady na wdrożenie i dalszy rozwój
- brak metod na sprawdzanie poprawności oprogramowania (jedynie testowanie do
pełnego wyeliminowania błędów).
Impulsem w kierunku przejścia od sprawdzania poprawności programów komputerowych
metodą prób i błędów do udowadniania, że posiada on pożądane własności (czyli jest poprawny)
był artykuł Johna McCarthyego  A basis for a mathematical theory of computation . Innymi
teoretykami byli: Dijkstra, Hoare, Floyd, Writh.
2. Podstawowe zasady analizy algorytmów
Układając algorytmy (programy) staramy się poznać ich własności. Chcemy wiedzieć
między innymi:
czy ułożony algorytm jest rzeczywiście rozwiązaniem postawionego problemu;
czy przeznaczony czas pracy komputera jest wystarczajÄ…cy
czy ilość miejsca w pamięci jest wystarczająca
jakie będą skutki po dokonaniu pewnych zmian w algorytmie, czy zmiany te nie
zmienią wyników
czy będzie działał dla każdej możliwej konfiguracji danych wejściowych.
Te i inne problemy spowodowały powstanie działu informatyki o nazwie Analiza
algorytmów, którego podstawowym zadaniem jest szukanie najlepszych algorytmów. Szukanie
to sprowadza się do znalezienia odpowiedzi na następujące trzy pytania:
Pytanie 1
Czy dany problem MOŻE BYĆ rozwiązany na komputerze w dostępnym czasie i dostępnej
pamięci?
Pytanie 2
Który ze znanych algorytmów jest najlepszy (ogólnie i dla konkretnego zestawu danych
wejściowych); czy jest on algorytmem optymalnym?
Pytanie 3
Jak udowodnić, że wybrany algorytm rozwiąże dany problem?
Analizując więc algorytmy należy zwrócić uwagę na jego :
poprawność semantyczną, czyli czy wykonuje on postawione zadania;
prostotÄ™;
czas działania;
ilość zajmowanej pamięci;
optymalność.
Przedstawione teraz będą metody analizy algorytmów, które są pomocne przy znajdowaniu
odpowiedzi na postawione wyżej pytania 1, 2 i 3.
A. Poprawność semantyczna,czyli algorytm rozwiąże postawione zadanie
Powiedzieliśmy wcześniej, że działanie algorytmu (oznaczmy go literą K ), zależy od
wartości początkowych otrzymanych z zewnątrz, czyli od tzw. danych wejściowych (ą).
Np. - dla algorytmu obliczającego NWP(m,n) będą to dwie liczby naturalne m oraz n .
- dla algorytmu znajdującego największy element w ciągu liczbowym (a1, ..., an),
będą to elementy tego ciągu oraz liczba n oznaczająca długość ciągu.
Natomiast wartości, które algorytm przekazuje na zewnątrz nazywane są danymi
wyjÅ›ciowymi (²) lub wynikiem algorytmu.
Np. - algorytm NWP(m,n) powinien podać jako wynik wartość największego wspólnego
podzielnika liczb m i n.
Mamy więc następujący układ:
warunek poczÄ…tkowy Ä…
(dane wejściowe)
Algorytm K
warunek koÅ„cowy ²
(dane wyjściowe)
Definicja
Mówimy, że algorytm K jest semantycznie poprawny względem warunków początkowego ą
i koÅ„cowego ², jeżeli:
- dla każdych danych wejściowych spełniających warunek ą obliczenia algorytmu K
dochodzą do punktu końcowego;
- koÅ„cowe wartoÅ›ciowanie zmiennych speÅ‚nia warunek ².
Przyjmujemy, ze: algorytm semantycznie poprawny a" algorytm poprawny.
OdwracajÄ…c zagadnienie, postawmy pytanie:
Kiedy algorytm jest niepoprawny ?.
Odpowiedzi mogą być również trzy:
Po pierwsze:
albo dochodzi do koÅ„ca, ale wyniki nie speÅ‚niajÄ… warunku koÅ„cowego ²
(z
le liczy)
Po drugie:
albo zatrzymuje się w punkcie niekońcowym algorytmu
(zawiesza siÄ™)
Po trzecie:
albo obliczenia algorytmu są nieskończone
(zapętla się).
Co więc trzeba wykazać, żeby stwierdzić, że analizowany algorytm jest poprawny?
Wystarczy pokazać, że dla każdych danych wejściowych spełniających warunek ą ma on
trzy następujące własności:
1) jeżeli obliczenie algorytmu K dochodzi do punktu końcowego, to otrzymane wyniki
speÅ‚niajÄ… warunek koÅ„cowy ²;
2) obliczenie algorytmu K nie jest przerwane;
3) obliczenie algorytmu K nie jest nieskończone.
Czy zawsze te wszystkie trzy warunki są jednocześnie spełnione?
Jeżeli dla algorytmu K spełniony jest tylko warunek:
Pierwszy to algorytm K jest
częściowo poprawny wzglÄ™dem warunku poczÄ…tkowego Ä… i warunku koÅ„cowego ²;
Drugi to algorytm K ma
własność określoności obliczeń względem warunku początkowego ą;
Trzeci to algorytm K ma
własność stopu względem warunku początkowego ą..
B. Metoda niezmienników
Metoda niezmienników:
służy do dowodzenia poprawności algorytmów
polega na opisywaniu własności wartościowań zmiennych otrzymywanych, gdy
obliczenie algorytmu przechodzi przez jego wyróżnione punkty ;własności te
nazywane są właśnie niezmiennikami algorytmu.
Przykład
Rozwazmy algorytm dzielenia całkowitego liczb naturalnych. Jego sformułowanie jest
następujace:
Dla dwóch liczb naturalnych x, y znalez
ć dwie liczby naturalne q oraz r takie, że:
x = q " y + r
gdzie q - iloraz całkowity dzielenia x przez y
r - reszta z tego dzielenia.
Np. dla x=11, y=4 mamy 11 = 2 * 4 + 3
czyli q=2 oraz r=3
Zapis algorytmu w pseudokodzie:
poczÄ…tek
{Ä…: 0d"x '" 0 d" y}
1: q:=0 ; r:=x ;
2: dopóki y<=r wykonuj
poczÄ…tek
q:=q+1 ; r:=r-y
koniec;
3: {² : x=q"y+r '" 0d"r < y
}
koniec;
Mamy więc:
Warunek poczÄ…tkowy Ä… : 0<=x '" 0<=y
Warunek koÅ„cowy ² : x=q*y+r '" 0d"rAlgorytm skÅ‚ada siÄ™ z dwóch części:
1. incjalizacji wartości zmiennych: q oraz r (etykieta 1)
2. iteracji dopóki , która oblicza iloraz q oraz resztę r z dzielenia całkowitego x przez y.
( etykieta 2)
Przeprowadzimy dowód na częściową poprawność tego algorytmu względem warunków ą i
². Polegać on bÄ™dzie a pokazaniu, że:
dla danych wejściowych spełniających warunek początkowy ą, jeżeli obliczenia dochodzą
do koÅ„ca , to wartoÅ›ci zmiennych x, y, q oraz r speÅ‚niajÄ… warunek koÅ„cowy ².
Postawmy w tym celu następujące pytanie:
Jaki warunek spełniają zmienne x, y, q oraz r w punkcie pośrednim algorytmu, tzn. w
etykiecie 2, a dokładniej,
jaki warunek spełniają te zmienne w chwili sprawdzania warunku  y<=r sterującego
iteracją dopóki?
Określmy w tym celu następujący nowy warunek
Å‚: x = q " y + r '" 0 d" r '" 0 d" y
jako niezmiennik naszej instrukcji warunkowej dopóki.
Pokażemy, że za każdym razem,
gdy obliczenie algorytmu rozpoczyna się ze stanem spełniającym warunek
początkowy ą orazdochodzi z wartościami x, y, q oraz r do sprawdzania
warunku iteracji  y<=r ,
wówczas
dla tych wartości zmiennych jest spełniony warunek ł.
Zauważmy, że istnieją tylko dwa przypadki dojścia obliczeń do etykiety 2 :
1) bezpośrednio od etykiety 1 i wtedy mamy
q=0, r=x,
a ponieważ z definicji warunku ą mamy, że 0d" x '" 0d"y,
to warunek Å‚: x=0*y+x=x '" 0d"r '" 0d"y
jest oczywiście spełniony
2) przy wyjściu od samej etykiety 2, gdy warunek zachodzi i powtarza się wykonanie
instrukcji iteracyjnej.
Załóżmy więc, że
- rozpoczynamy działanie od etykiety 2
- spełnione są warunki
Å‚: x = q " y + r '" 0 d" r '" 0 d" y
oraz
warunek iteracji:  y<=r
Wykonuje się wtedy instrukcja złożona, która
- zmiennej q nadaje nową wartość q =q+1
- zmiennej r nadaje nową wartość r =r-y
A wtedy mamy dla warunku Å‚:
Å‚(x, y, q , r ) a" x=q *y+r 0d"r '" 0d"y
a" x=(q+1)*y+r-y i 0d"r-y '" 0d"y
Ponieważ:
1) (q+1)*y+r-y=q*y-r=x
więc 1-szy czynnik warunku ł jest spełniony;
2) 0d"r-y jest też prawdziwy, bo wiemy, że yd"r z założenia warunku iteracyjnego, czyli
0d"r-y
3) czynnik 0d"y jest też spełniony, ponieważ założono, że warunek  0d"y zachodzi w ą ,a
wartość zmiennej y nie ulega zmianie.
Stosując indukcję względem liczby wykonywanych sprawdzeń warunku iteracji  yd"r (tj.
liczby przejść obliczeń przez etykietę 2), wnioskujemy, że przy każdym sprawdzeniu warunku
iteracji zachodzi warunek Å‚.
Mogą teraz zajść dwa przypadki:
1) Warunek iteracyjny  yd"r pozostaje ciągle spełniony i wtedy obliczenie NIGDY nie
dochodzi do etykiety 3;
2) W pewnej chwili przy sprawdzaniu warunku iteracji mamy y>r i obliczenie
przechodzi do etykiety 3.
Ponieważ wtedy spełniony jest również warunek ł, co przy fakcie, że y>r daje nam
prawdziwość warunku końcowego
x=q"y+r
'" d"
²: '" 0d"r'" d"
'" d"
Udowodniliśmy więc następujący fakt:
Ä…
jeżeli obliczenie algorytmu startuje z danymi wejściowymi spełniającymi warunek ą i
Ä…
Ä…
²
dochodzi do punktu koÅ„cowego, to otrzymane wyniki speÅ‚niajÄ… warunek koÅ„cowy ².
²
²
Oznacza to, że algorytm jest częściowo poprawny wzglÄ™dem warunków Ä… i ².
Nie jest on jednak poprawny, bo np. dla danych: x=0, y=0 jego obliczenia są nieskończone
(brak własności stopu!)
Uogólniając, metoda niezmienników polega na:
1) wyróżnieniu w programie pewnych szczególnych miejsc
2) przypisaniu do nich warunków na wartościowanie zmiennych algorytmu
3) udowodnieniu, że
jeżeli początkowy stan obliczenia spełnia warunek początkowy ą, to ilekroć obliczenie
algorytmu dochodzi do wyróżnionego miejsca, zawsze przyporządkowany temu miejscu
warunek jest spełniony przez aktualne wartościowanie zmiennych.
W szczególności, gdy dochodzi do punktu końcowego, to wartościowanie zmiennych
speÅ‚nia warunek koÅ„cowy ²
Należy zwrócić uwagę na to, że bardzo istotny jest wybór wyróżnionych miejsc (czyli
niezmienników) w analizowanej instrukcji.
Na przykład:
dla instrukcji typu dopóki jest to miejsce sprawdzania warunku sterującego iteracją
dla instrukcji typu powtarzaj sÄ… to dwa miejsca:
- poczÄ…tek instrukcji
- -miejsce sprawdzania warunku sterujÄ…cego iteracjÄ…
C. Dowodzenie własności stopu
Stosuje siÄ™ dwie metody dowodzenia:
1) Metoda liczników iteracji
- wprowadzenie dodatkowej zmiennej całkowitej służącej do obliczania liczby wykonań
instrukcji iteracyjnej (licznik wykonań iteracji)
szuka się wyrażenia, którego wartość w trakcie realizacji algorytmu ograniczyłaby z
góry wartość tej zmiennej (licznika)
W przypadku rozpatrywanego algorytmu dzielenia:
poczatek Ä… 1 : x e" 0 i y > 0}
{
1: q:=0; r:=x
2: dopóki re"y wykonuj
poczÄ…tek
q:=q+1; r:=r-y
koniec
{²
3: : x = q"y+r i 0 d" r <}
zmienna q pełni rolę licznika iteracji dopóki; mamy zatem, że górna ilość wykonań iteracji
wynoai qd"ðÅ‚x/yûÅ‚
2) Metoda malejących wielkości
- rozpatruje się takie wielkości (wyrażenia arytmetyczne), które zwiększają (lub
zmniejszają) swoją wartość w sposób nieregularny i dla których istnieje wartość
ograniczająca je z góry (lub z dołu).
-
Przykład
Numeryczny algorytmy przybliżonego rozwiązywania równania nieliniowego metodą
bisekcji wykonuje iteracje tak długo, aż przedział zawierający pierwiastek tego równania
osiÄ…gnie zamierzonÄ… szerokość µ>0 .
3. ZA
OŻONOŚĆ OBLICZENIOWA
Każde wykonanie algorytmu na komputerze wymaga pewnej pracy oraz pewnej ilości
miejsca w jego pamięci. Dlatego też przed kodowaniem algorytmu do postaci akceptowanej
przez komputer, jego testowaniem a następnie użytkowaniem, powinniśmy odpowiedzieć sobie
na pytanie:
Czy nasz sprzęt umożliwia stosowanie rozważanego algorytmu dla przewidywanych
danych?
Okazuje się bowiem, że dla wielu znanych algorytmów czas ich działania zwiększa się zbyt
szybko w miarę, jak wzrasta wielkość danych wejściowych. Dokonując oceny różnych
algorytmów rozwiązujących dane zagadnienia chcemy wiedzieć, jaka jest ich złożoność
obliczeniowa, czyli inaczej, jaka ilość zasobów komputerowych potrzebna jest do ich
wykonania.
Za podstawowe zasoby komputerowe uważa się:
- czas działania algorytmu
- ilość zajmowanej pamięci.
Chcemy jednak, żeby te dwie wartości (czas i pamięć) były na tyle reprezentatywne, by np.
użytkownik małego komputera osobistego oraz użytkownik potężnego superkomputera,
używający tego samego algorytmu - mogli się porozumieć do do jego sprawności obliczeniowej.
Czy bowiem stwierdzenie:
Mój program (algorytm) jest szybki, bo rozwiązał zadanie w 55 sekund !
może posłużyć za obiektywną ocenę jego sprawności ?
Dodatkowo powinniśmy bowiem wiedzieć:
- na jakim komputerze program był wykonywany
- jaki miał procesor (częstotliwość zegara)
- co działo się w pamięci komputera podczas jego wykonywania
- jakiego kompilatora użyto do napisania programu, itp.
StÄ…d wynika oczywisty wniosek:
Ocena sprawności algorytmu przy pomocy kryteriów sprzętowych nie jest oceną
obiektywnÄ…!
Należy więc znalez
ć miarę uniwersalną, która ma decydujący wpływ na czas
wykonywania określonego algorytmu. Parametrem tym jest rozmiar danych wejściowych
algorytmu.
Pojęcie to ma różne znaczenie dla różnych zagadnień, np.:
- w sortowaniu ciągu n-elementowego jest to ilość elementów tego ciągu, czyli n.
- dla zadań grafowych jest to liczba krawędzi rozpatrywanego grafu
- przy wyznaczaniu wartości wielomianu - stopień tego wielomianu
- dla operacji na macierzach - wymiary macierzy
- dla wyliczenia wartości funkcji n! -wartość danej n.
Przed przystąpieniem do wyznaczania złożoności obliczeniowej algorytmów należy jeszcze
określić jednostki, w jakich będzie ona liczona.
Dla złożoności pamięciowej jednostką taką będzie słowo pamięci i jest to sprawa oczywista.
Dla złożoności czasowej problem jest bardziej złożony, ponieważ jednostka ta powinna
być własnością samego tylko algorytmu jako metody rozwiązania problemu, a nie powinna
zależeć od komputera, języka programowania, kodowania , itp.
W tym celu wyróżnia się w klasie algorytmów charakterystyczne dla niego operacje -
nazywane sÄ… one operacjami dominujÄ…cymi.
Przykłady operacji dominujących:
w algorytmach sortowania
- porównanie dwóch elementów w ciągu wejściowym
- przestawienie dwóch elementów w ciągu
w algorytmach numerycznych, np. obliczania wartości wielomianu
- operacje arytmetyczne: +, -, /, *
w algorytmach przeglÄ…danie drzewa binarnego
- przejście dowiązania pomiędzy dwoma węzłami w drzewie.
Za jednostkę złożoności czasowej przyjmuje się wykonanie jednej operacji dominującej.
Zanim przejdziemy do szczegółowego omówienia własności funkcji złożoności czasowej,
postawmy następujące pytanie:
Czy postęp w szybkości obliczeń komputerów zmniejsza znaczenie efektywności
algorytmów?
W celu ilustracji odpowiedzi na to pytanie rozważmy pięć algorytmów A1, A2,..., A5,
rozwiązujących ten sam problem i mających następujące złożoności czasowe:
Algorytm Złożoność czasowa f(n) f(n=10)
A1 n 10
A2 n*logn
H"33
A3 n2 100
A4 n3 1000
A5 2n 1024.
gdzie n - rozmiar danych wejściowych.
Zakładając, że jednostką czasu jest jedna milisekunda, pokażemy, jakiego maksymalnego
rzędu zadania mogą rozwiązać te algorytmy odpowiednio w: 1 sekundzie, 1 minucie, 1 godzinie.
Algorytm Złożoność czasowa Maksymalny rozmiar zadania
1sek 1min 1godzina
A1 n 1000 6x104
3,6Å"106
A2 nlogn 140 4893
2,0Å"105
A3 n2 31 244 1897
A4 n3 1039153
A5 2n 9 1521
Przypuśćmy teraz, że nowa generacja komputerów jest 10-krotnie szybsza. Pokażemy, jaki
jest wzrost rozmiaru zadań, które mogą być rozwiązane dzięki wzrostowi szybkości
komputerów:
Algorytm Złożoność Maksymalny rozmiar Maksymalny rozmiar
czasowa zadania przed zadania po
przyśpieszeniem przyśpieszeniu
A1 n S1 10S1
A2 n*logn S2 około 10S2 dla dużych
n
A3 n2 S3 3.16 S3
A4 n3 S4 2.15 S4
A5 2n S5 S5 + 3.3
Zauważamy, że np.:
- dla A5 10-krotny wzrost szybkości pozwolił zwiększyć zadania tylko o 3;
- dla A3 rozmiar ten wzrósł więcej niż 3-krotnie
- dla A1 rozmiar wzrósł 10-krotnie, czyli tyle, ile wzrosła prędkość komputera
Traktując 1 minutę jako podstawę porównania można łatwo stwierdzić, że:
- zastępując A4 przez A3 możemy rozwiązać zadanie 6 razy większe
- zastępując A4 przez A2 możemy rozwiązać zadanie 125 razy większe
jest to lepsze niż 2-krotne zwiększenie zadania uzyskane przez 10-krotny
wzrost szybkości komputera.
WNIOSEK: Bardziej opłacalne jest konstruowanie szybszych algorytmów.
Rozpatrywane wyżej funkcje złożoności czasowej są tzw. złożonościami asymptotycznymi,
tzn. nie uwzględniają stałej proporcjonalności. Może się, więc zdarzyć, że analizując faktyczne
funkcje złożoności czasowej, (dokładnie wyznaczone), algorytm asymptotycznie gorszy jest
szybszy dla małych zadań niż algorytm asymptotycznie lepszy.
Dla ilustracji przypuśćmy, że rozważane algorytmy A1, ..., A5 mają następujące faktyczne
funkcje złożoności czasowej:
Algorytm Funkcje złożoności czasowej Kiedy najszybsze
A1 1000 n n>1024
A2 100 n*logn
59d" d"
d" n d"1024
d" d"
d" d"
A3 10 n2
10d" d"
d" n d"58
d" d"
d" d"
A4 n3
A5 2n
2d" d"
d" n d"9
d" d"
d" d"
Wyznaczając złożoność czasową algorytmu (jest to funkcja rozmiaru danych n) rozróżniamy
jej dwie postacie:
1) złożoność pesymistyczna
- ilość operacji dominujących potrzebnych przy trafieniu na  najgorsze dane wejściowe
rozmiaru n
2) złożoność oczekiwana
- ilość operacji dominujących potrzebnych przy  typowych danych wejściowych
rozmiaru n.
Formalne definicje tych pojęć są następujące:
Przez pesymistyczną złożoność czasową algorytmu rozumie się funkcję:
{}
W(n) = sup t(d) : d "Dn
gdzie: sup - kres górny zbioru
Dn - zbiór wszystkich możliwych zestawów danych wejściowych rozmiaru n
t(d) - liczba operacji dominujących dla zestawu danych wejściowych d
Przez oczekiwaną złożoność czasową algorytmu rozumie się funkcję:
= "
A(n) k p
" nk
k e" 0
gdzie: pnk - rozkład prawdopodobieństwa zmiennej losowej Xn, tzn. prawdopodobieństwo, że
dla danych rozmiaru n algorytm wykona k operacji dominujÄ…cych (ke"0),
Xn jest zmienną losową, której wartością jest t(d), dla d"Dn
czyli jest to wartość oczekiwaną ave(Xn) zmiennej losowej Xn.
W celu stwierdzenia, na ile funkcje W(n) i A(n) sÄ… reprezentatywne dla wszystkich danych
wejściowych rozmiaru n, rozważa się dwie wrażliwości algorytmu:
miarę wrażliwości pesymistycznej:
" (n) = sup {t(d1)- t(d ): d1, d " D }
2 2 n
miarę wrażliwości oczekiwane:
´ (n) = dev(X )
n
gdzie dev(Xn) jest standardowym odchyleniem zmiennej losowej Xn, tzn.
=
dev(Xn ) var(Xn )
i var(Xn ) = -ave(Xn ))2 Å"pnk ,
"(k
ke"0
var(Xn) oznacza wariancjÄ™ zmiennej losowej Xn.
Jak należy interpretować wartoÅ›ci wrażliwoÅ›ci "(n) i ´(n):
" ´
" ´
" ´
" ´
Im wiÄ™ksze wartoÅ›ci "(n) i ´(n), tym algorytm jest bardziej wrażliwy na dane wejÅ›ciowe
" ´
" ´
i tym bardziej jego zachowanie w wypadku rzeczywistych danych może odbiegać od
zachowania opisanego funkcjami W(n) i A(n).
Przykład:
Algorytm przeszukiwanae sekwencyjnego ciÄ…gu.
Problem: Dla podanego n-elementowego ciągu liczb naturalnych oraz liczby x sprawdzić, czy
liczba x jest elementem tego ciÄ…gu.
Dane wejściowe:
n, (ne" liczba naturalna
e"0)
e"
e"
L[1..n+1] tablica z elementami ciÄ…gu (a1, ..., an) na miejscach od 1do n ,
x poszukiwany element.
Dane wyjściowe (wynik):
zmienna logiczna p taka, że
p= prawda gdy element x należy do ciągu
p= fałsz, gdy element x nie należy do ciągu
Zapis algorytmu w pseudokodzie:
poczÄ…tek
j := 1;
L[n+1] := x;
dopóki L[j] # x wykonuj j:= j+1;
p := jd"n
koniec;
Realizacja algorytmu (zestaw danych 1)
Dla: n=4; ciÄ…gu (1,4,2,8), x=4 mamy:
L[1]=1, L[2]=4, L[3]=2, L[4]=8
j=1 , L[5]=4
1 # 4, TAK j=1+1=2 ( L[1]#4 )
4 # 4, NIE ( L[2)#4 )
p=2d"4 (prawda)
Realizacja algorytmu (zestaw danych 2)
Ddla: n=4; ciÄ…gu (1,4,2,8), x=5 mamy
L[1]=1, L[2]=4, L[3]=2, L[4]=8
j=1 L[5]=5
1#5, TAK j=1+1=2 (L[1]#5 )
4#5, TAK j=2+1=3 (L[2]#5 )
2#5, TAK j=3+1=4 (L[3]#5 )
8#5, TAK j=4+1=5 (L[4]#5 )
5#5, NIE (L[5]#5 )
p=5d"4 (falsz)
Analiza złożoności algorytmu:
Rozmiar danych wejściowych : n
Operacje dominujące : porównania L[j])#a
Pesymistyczna złożoność czasowa : W(n)=n+1
Pesymistyczna wrażliwość czasowa: "(n)=n
"
"
"
bo najwięcej porównań n+1
bo najmniej porównań 1
stÄ…d "(n)=(n+1)-1=n
Jaka jest więc oczekiwana złożoność czasowa ?
Niech prawdopodobieństwo znalezienia elementu x na każdym z n możliwych miejsc
jest takie samo, oraz element x należy do ciągu (a1,.... an), tzn.
1
p = dla k = 1,2,...n
nk
n
Wówczas
n n n
n(n+1)
1 1 1 n+1
A(n) =
"kÅ"p = "kÅ" = "k = =
nk n n n 2 2
k=1 k=1 k=1
Do obliczenia oczekiwanej wrażliwości czasowej należy znalez
ć wcześniejsze wariancje
zmiennej losowej Xn
n n
2 2 2
n(n+1)(2n+1) 2(n+1) n(n+1)
n+1 1 1 n+1
()=
var(Xn ) = - ave(Xn )) Å" pnk = - ) Å" = - + n Å"( )
"(k "(k
2 n n 6 2 2 2
k=1 k=1
n(n+1)(2n+1) (n+1)2 n+1
n2-1 1
= - = (4n + 2 - 3n - 3)= H" n2
6 4 12 12 12
1 n n
´(n) = dev(Xn ) = var(Xn) = n2 = H" H" 0,25n
i teraz
12 3,464
12
Wniosek:
Funkcja wrażliwości i funkcja złożoności są liniowe, a więc mocno wrażliwe na układ
danych wejściowych.
Jest oczywiste, że faktyczna złożoność czasowa algorytmu w chwili jego użycia różni się od
wyliczonej teoretycznie, pewnym współczynnikiem proporcjonalności lub pewnymi
elementami stałymi. Ponieważ analiza złożoności interesuje się głównie zależnością
efektywności algorytmu (czasu działania) od rozmiaru problemu w sytuacji, gdy ten ostatni
wzrasta nieograniczenie, nie jest istotna dokładna formuła tej zależności, lecz jej zachowanie
asymptotyczne. Pomijamy w niej stałe elementy i inne, pozostawiając jedynie najbardziej
znaczące składniki formuły, czyli te, które decydują o zachowaniu się formuły, gdy rozmiar n
dąży do nieskończoności.
Reasumując, istotną częścią informacji, która jest zawarta w funkcji złożoności czasowej
W(n) jest jej rząd wielkości, czyli jej zachowania asymptotyczne, gdy n dąży do
nieskończoności. Poniżej omówione będą pewne pojęcia związane z tym zagadnieniem.
Niech f, g, h : NR+ *" {0}, gdzie N - zbiór liczb naturalnych
R+ - zbiór liczb rzeczywistych dodatnich
będą trzema dowolnymi funkcjami.
NOTACJA O
Mówimy, że funkcja f jest co najwyżej rzędu funkcji g, co zapisujemy jako
f(n)= O (g (n))
jeżeli istnieje stała rzeczywista c>0 i stała naturalna n0 takie, że
d" Å"
f(n) d" c Å"g(n), dla każdego ne"n0
d" Å"Å"
d"
Å"
cÅ"g(n)
Å"Å"
f(n)
no n
f(n) = O(g(n))
Np. Dla (n) = n2 +2n mamy, że n2 +2n=O(n2), bo istnieje stała c=3>0 i stała
naturalna no=1 takie, że
n2 +2n d" 3Å"
d" Å"Å"
d" Å" n2 = 3g(n) dla każdego n e" 1Å" i g(n)= n2
d"
Czyli f(n) = n2 +2n jest co najwyżej rzędu O(n2)
NOTACJA &!
&!
&!
&!
Mówimy, że funkcja f jest co najmniej rzędu funkcji g, co zapisujemy jako
&!
f(n) = &!(g(n))
&!
&!
jeżeli istnieje stała c>0 i stała naturalna no, takie, że
Å" d" e"
cÅ"g(n) d" f(n) dla każdego ne" no .
Å"Å" d" e"
d" e"
Inaczej mówiąc: g(n) = O(f(n))
f(n)
Å"
cÅ"g(n)
Å"Å"
no n
f(n) = &!
&!(g(n))
&!
&!
NOTACJA Åš
Mówimy, że funkcja f jest dokładnie rzędu funkcji g, co zapisujemy jako
Åš
f(n) = Åš(g(n))
Åš
Åš
jeżeli istnieja stałe c1>0, c2>0 oraz stała naturalna no, takie, że
Å" d" d" Å"
c1Å"g(n) d" f(n) d" c2Å"g(n)dla każdego ne" no
Å"Å" d" d" Å"Å"
d" d"
&!
Czyli inaczej f(n) = O(g(n)) i f(n) = &!(g(n)).
&!
&!
Å"
c2Å"g(n)
Å"Å"
f(n)
Å"
c1Å"g(n)
Å"Å"
n
no
Åš
f(n) = Åš(g(n))
Åš
Åš
2
2 1n
1
( )
Np. Dla funkcji mamy, że f(n)= -3n=Åšn2 ponieważ istniejÄ… staÅ‚e c1Å">0,
f(n)= -3n
2n 2
c2Å">0 i no, dla których
2 2 2
1
dla każdego ne"no
c n d" n - 3n d" c n
2
1 2
1
Można bowiem sprawdzić, że dla c 14 , c 1 , no 7 zachodzi nierówność
= = =
2
1 2
1 1 1
n2 d" n2 - 3n d" n2 dla n e" 7.
14 2 2
Do porównania rzędów wielkości dwóch danych funkcji f(n) i g(n) można wykorzystać
obliczenia następującej granicy:
f(n)
E = lim" g(n)
n
Jeżeli
E=+", to g(n) = O(f(n)) ale NIE f(n)=O(g(n))
Åš
E=c>0, to f(n) = Åš(g(n))
Åš
Åš
E=0, to f(n) = O(g(n)) ale NIE g(n)=O(f(n)).
Np. Dla f(n)=nlogn, g(n)=n2
f(n) nlogn
lim = lim = 0
n" n"
g(n)
n2
czyli n·logn=O(n2) ale nie n2=O(n logn)
Większość ze znanych algorytmów ma złożoność czasową należącą do podanego niżej
wykazu. To, że funkcji tych jest raczej mało, wynika z własności  pochłaniania przez  duże
O stałych współczynników i wyrazów niższego rzędu.
Np. Funkcje:
n3, 5 n3+2 n2-100n+5, 6 n3+4·n·log(n)+2
są rzędu O(n3)
Wykaz podstawowych złożoności czasowych
- złożoność logarytmiczna
- np. algorytmy, w których zadanie rozmiaru n sprowadzane jest do
logn
zadania rozmiaru n/2, plus pewna stała liczba działań
np. przeszukiwanie binarne
- złożoność liniowa
- np. algorytmy, w których dla każdych n-elmentowych danych
n
wejściowych wykonywana jest stała liczba działań
 np. algorytm Hornera obliczania wartości wielomianu
- złożoność nlogn (liniowo-logarytmiczna)
- np. algorytmy, w których zadanie rozmiaru n zostaje sprowadzone do
dwóch podzadań rozmiaru n/2, plus pewna liczba działań liniowa
Å"
nÅ"logn
Å"Å"
względem rozmiaru n, potrzebnych do wykonania najpierw rozbicia a
następnie scalenia rozwiązań podzadań rozmiaru n/2 w rozwiązanie
rozmiaru n
np. sortowanie przez scalanie
- złożoność kwadratowa
- np. algorytmy, w których jest wykonywana pewna stała liczba działań
n2
dla każdej pary danych wejściowych (mają podwójną iterację
np. wyzerowanie elementów tablicy 2-wymiarowej
- dalsze złożoność wielomianowe
n3, n4
- złożoność podwykładnicza
logn
n
- złożoność wykładnicza
2n
- np. algorytmy, w których jest wykonywana stała liczba działań, dla
każdego podzbioru danych wejściowych
- złożoność wykładnicza n!
- np. algorytmy, w których jest wykonywana stała liczba działań, dla
n!
każdej permutacji danych wejściowych.
W celu uświadomienia sobie jak różne rodzaje złożoności czasowej wpływają na sens
stosowania ich do rozwiązywani problemów o dużym rozmiarze przeanalizujmy następujące
zestawienia.
Przyjmijmy, że komputer, na którym wykonujemy te algorytmy może wykonać 1 milion
operacji na 1 sek.
n=10 n=20 n=30 n=40 n=50
n3 0,001s 0,008s 0,027s 0,064s 0,125s
2n 0,001s 1,05s 17,9m 1,27d 35,7r
3n 0,059s 58,1m 6,53r 3,86·105r 2,28·1010r
n! 3,63s 7,71·104r 8,41·1018r 2,59·1034r 9,64·1050r
dla n!=24! czas jest większy niż obecny wiek wszechświata.
3.Rekurencja (rekursja)
Wiele ważnych algorytmów ma strukturę rekurencyjną, którą można opisać
następująco:
W celu rozwiązania danego problemu algorytm wywołuje sam siebie w sposób
bezpośredni lub pośredni.
Zastosowanie rekursji często prowadzi do bardziej zrozumiałych i zwięzłych opisów
algorytmów, niż było to możliwe bez rekursji. Do obliczenia złożoności czasowej algorytmów
rekurencyjnych stosujemy równania rekurencyjne. Przykład takiego równania wraz z
rozwiązaniem będzie podany w dalszej części.
Często zdarza się, że w celu rozwiązania pewnego problemu dzielimy go na podproblemy.
Następnie znajdujemy rozwiązania podproblemów  są one prostsze niż rozwiązania problemu
złozonego- i za ich pomocą znajdujemy rozwiązanie problemu wyjściowego.
Metoda ta, zwłaszcza stosowana rekurencyjnie, prowadzi często do efektywnych
algorytmów rozwiązujących takie problemy, których podproblemy mają identyczną postać, ale
sÄ… za to mniejszego rozmiaru.
Taka metoda konstrukcji algorytmów nazywana jest metodą  dziel i zwyciężaj (ang. divide
and conquer).
Składa się ona z trzech etapów:
1) DZIEL : dzielimy problem na podproblemy
2) ZWYCI
ŻAJ : rozwiązujemy podproblemy rekurencyjnie
3) POA

CZ : łączymy rozwiązania podproblemów, aby otrzymać rozwiązanie
wyjściowego problemu.
Technikę  dziel i zwyciężaj zilustrujemy dwoma przykładami:
Przykład 1
Problem: Dana jest tablica n liczb całkowitych a[1], ..., a[n].
Czy w tablicy występuje element x ?
RozwiÄ…zanie:
Dziel: Podzielimy tablice na dwie części:
CZ
ŚĆ I: pierwszy element tablicy, tzn. a[1]
CZ
ŚĆ II: pozostałe (n-1) elementów, tzn. a[2], ..., a[n]
Zwyciężaj: Jeżeli pierwszy element jest równy x, to wynikiem jest napis  TAK
WYST
PUJE
i kończymy obliczenia,
w przeciwnym razie
sprawdzamy, czy x występuje w pozostałych n-1 elementach (czyli w
części II)
Podane zostały warunki tylko pozytywnego zakończenia problemu. W przypadku, gdy
przebadaliśmy całą tablicę i element x nie został znaleziony, to działanie algorytmu powinno się
zakończyć wraz z podaniem napisu  NIE ZNALEZIONO .
Realizacja rozwiązania problemu w postać programu może być następująca.
SZUKAJ ([a1, ..., an], lewy, prawy, x)
{lewy- oznacza lewÄ…, prawy- oznacza prawÄ… granicÄ™ przeszukiwanego obszaru
tablicy;
na poczatku lewy=1, prawy=n}
poczÄ…tek
jeżeli lewy > prawy to  BRAK W CI
GU
w przeciwnym razie
jeżeli a[lewy]=x to  JEST W CI
GU
w przeciwnym razie SZUKAJ([a1, ..., an], lewy+1, prawy, x)
koniec
Warunkiem zakończenia algorytmu jest:
albo znalezienie szukanego elementu :( a[lewy]=x )
albo wyjście poza obszar poszukiwany :(lewy>prawy).
Przykładowe realizacjealgorytmów dla dwóch zestawów danych:
1) dla ciÄ…gu: 0, 7, 8, 5 i szukanego elementu: x=8 dostajemy
SZUKAJ ([0,7,8,5],1,4,8) {ciÄ…g,lewy=1, prawy=4, x=8}
Ó!
1>4 Nie ( czy lewy>prawy ? )
0=8 Nie ( czy a[1]=x ? )
SZUKAJ ([0,7,8,5],2,4,8)
Ó!
2>4 Nie ( czy lewy>prawy ?)
7=8 Nie ( czy a[2]=x ? )
SZUKAJ ([0,7,8,5],3,4,8)
Ó!
3>4 Nie ( czy lewy>prawy ? )
8=8 Tak ( czy a[3]=x ? )
“! JEST W CI
GU
“!
“!
“!
2) dla ciÄ…gu : 0, 7, 8, i szukanego elementu: x=5 dostajemy:
SZUKAJ ([0,7,8],1,3,5) {ciÄ…g,lewy=1, prawy=3, x=5}
Ó!
1>3 Nie ( czy lewy>prawy ? )
0=5 Nie ( czy a[1]=x ? )
SZUKAJ ([0,7,8],2,3,5)
Ó!
2>3 Nie ( czy lewy>prawy ?)
7=5 Nie ( czy a[2]=x ? )
SZUKAJ ([0,7,8],3,3,5)
Ó!
3>3 Nie ( czy lewy>prawy ? )
8=5 Nie ( czy a[3]=x ? )
SZUKAJ ([0,7,8],4,3,5)
Ó!
4>3 Tak ( czy lewy>prawy ? )
“! BRAK W CI
GU
“!
“!
“!
Algorytm ten posiada dwie ważne cechy algorytmów rekurencyjnych:
1) zakończenie rekurencji jest jasno określone:
- znaleziono element ( a[lewy]=x )
lub
- przekroczono zakres tablicy ( lewy>prawy )
2) duży problem został rozbity na dwa mniejsze
1-szy - elementarny
2-gi - na analogiczny problem, tylko o mniejszym rozmiarze
Przykład 2
Problem: Znalez
ć największy i najmniejszy element w zbiorze n-elementowym S. Załóżmy
dodatkowo, że n jest potęgą liczby 2.
RozwiÄ…zanie:
DZIEL: Podziel zbiór S na dwa podzbiory S1 i S2, z których każdy zawiera n/2
elementów.
ZWYCI
ŻAJ: Znajdz
minimalne i maksymalne elementy w zbiorach S1 i S2 a następnie
wybierz element mniejszy z dwóch znalezionych minimów i element
większy z dwóch znalezionych maksimów.
Procedura realizująca ten algorytm może mieć następującą formę:
MAXMIN(S);
{ S- dany zbiór elementów }
poczÄ…tek
1. jeżeli |S|=2 wtedy { |S| oznacza moc zbioru S }
poczÄ…tek
2. { niech S={a, b} }
3. powrót (MAX(a,b), MIN(a,b))
koniec
w przeciwnym razie
poczÄ…tek
4. podziel S na dwa rozłączne równoliczne podzbiory S1 i S2,
5. (max1, min1):= MAXMIN(S1 );
6. (max2, min2):= MAXMIN(S2 );
7. powrót (MAX(max1, max2), MIN(min1, min2)
 koniec
koniec
Zauważmy, że wywoływanie rekurencji zostaje zastopowane, gdy zbiór, który mamy
podzielić, zawiera dokładnie 2 elementy!
Obliczymy teraz funkcję złożoności czasowej. Jako operację dominującą przyjmijmy
porównanie dwóch elementów zbioru S. Porównania te wykonują się w instrukcji 3 i 7.
Oznaczmy przez T(n) liczbę porównań między elementami zbioru S, które wykonuje
procedura MAXMIN w celu znalezienia maksymalnego i minimalnego elementu w zbiorze n-
elementowym.
Mamy T(2)=1 dla n=2. (instrukcja 3)
natomiast dla n>2, T(n) jest równe całkowitej liczbie porównań wykonanych w
dwu wywołaniach MAXMIN (linie 5 i 6) dla zbiorów rozmiaru n/2, plus dwa
porównania z linii 7.;l
Dostajemy, więc
1 dla n = 2
Å„Å‚
T(n) =
òÅ‚2T(n/2) + 2 dla n > 2
ół
Można pokazać, ze rozwiązaniem tego równania rekurencyjnego jest funkcja:
3
T(n) = Å" n - 2.
2
a więc T(n)=O(n).
Klasycznym przykładem algorytmu rekurencyjnego jest obliczanie funkcji SILNIA (
ozn. n! )
Definicja funkcji n! jest następująca:
0! = 1
n! = 1Å"2Å".....Å"(n-1) Å"n
co można łatwo zapisać w postaci rekurencyjnej:
1 dla n d" 0
Å„Å‚
n!=
òÅ‚
ółn Å" (n -1) ! dla n < 0
Przykładowy algorytm można przedstawić następująco:
Funkcja SILNIA(n);
poczÄ…tek
jeżeli nd"0 wtedy pisz (1)
w przeciwnym wypadku
pisz (n*SILNIA(n-1))
koniec
Schemat realizacji funkcji SILNIA(3) jest następujący.
SILNIA(3)
Å"
3!=3Å"2=6
Å"Å"
3d"0 NIE 3!=3Å"2!
Ä™!
Ä™!
Ä™!
Ä™!
Ó!
Å"
2!=2Å"1=2
Å"Å"
2d"0 NIE 2!=2Å"1!
Ä™!
Ä™!
Ä™!
Ä™!
Ó!
Å"
1!=1Å"1=1
Å"Å"
1d"0 NIE 1!=1Å"0!
Ä™!
Ä™!
Ä™!
Ä™!
Ó!
0!=1
0d" 0 TAK
Dla n=0 nie następuje wywołanie rekurencyjne,
Dla n>0 kolejne wywołania odbywają się dla malejących systematycznie wartości argumentu
aż do wywołania z argumentem 0, który zatrzymuje całą rekursję.
OGÓLNIE:
zależność, której spełnienie przez algorytm wywołania gwarantuje uniknięcie dalszej
rekursji, nazywamy przypadkiem bazowym (ang. base case), lub warunkiem stopu rekursji
(ang. stopping case).
Jedną z konsekwencji każdego wywołania rekursywnego jest zajęcie pewnego obszaru
pamięci, który jest wykorzystywany przez stos, na którym zapamiętywane są wyniki kolejnych,
jeszcze nie zakończonych wywołań procedury. Stos podzielony jest na fragmenty stosu, będące
blokami kolejnych miejsc pamięci- każdy fragment zawiera dane o jednym trwającym
wywołaniu procedury. W przypadku bardzo dużej liczby wywołań rekurencyjnych szybko może
nastąpić przepełnienie stosu, a w konsekwencji przerwanie pracy procedury.
Przykładem takiej  kłopotliwej procedury rekurencyjnej jest procedura generowania n-
tego wyrazu ciÄ…gu Fibonacciego
CiÄ…g Fibonacciego
Definicja ciągu Fibonacciego jest następująca:
f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2) dla ne"2.
Przykładowe początkowe wyrazy: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
Rekurencyjna funkcja obliczającą n-ty wyraz tego ciągu ma postać:
Funkcja Fibo(n);
poczÄ…tek
jeżeli nd"1 wtedy Fibo:=1
w przeciwnym razie Fibo:=Fibo(n-1) + Fibo(n-2)
koniec;
Prześledz
my schemat wywołań funkcji Fibo dla n=4
F(4)
F(3) F(2)
F(2) F(1) F(1) F(0)
F(1) F(0)
F(4) = F(3) + F(2) = F(2) + F(1) + F(1) + F(0) = F(1) + F(0) + F(1) + F(1) + F(0) = 2F(0) +
3F(1) =
= (1+1) + (1+1+1) = 2 + 3 = 5
Widać tu wyraz
nie, że pewna część obliczeń wywoływana jest wielokrotnie - 3-razy F(1) i 2-
razy F(0).
Algorytm ten ma złożoność czasową: T(n)=(1,6)n. Przyczyną tak dużej złożoności
czasowej jest wielokrotne obliczanie tych samych wartości. Np.
dla n=30 wyraz F(30) ma 832040 wywołań funkcji F(0) i F(1),
natomiast odpowiadający mu algorytm iteracyjny ma tylko 30 dodawań !!!
Problem stopu rekursji
W wielu algorytmach rekurencyjnych, z pozoru poprawnie skonstruowanych, może być
ukryty poważy błąd polegający na nieskończonej ilości wywołań rekurencyjnych, czyli błędnie
sformułowanego warunku stopu.
Przeanalizujmy nastepujący przykład:
Funkcja Dokoncaswiata(n);
poczÄ…tek
jeżeli n=1 wtedy pisz(1)
w przeciwnym przypadku
jeżeli n mod 2=0 { n jest parzysta }
wtedy pisz( Dokoncaswiata(n-2)*n )
w przeciwnym razie pisz( Dokoncaswiata(n-1)*n )
koniec;
Z pozoru wszystko jest poprawne, bowiem:
1) jest przypadek bazowy (stop)
2) problem rzędu n jest upraszczany do problemu o rozmiarze niższym: n-1 lub n-2.
Dokładna analiza pokazuje jednak, że dla ne" wszystkie wywołania funkcji kończą się
e"2
e"
e"
parzystą wartością n, a to oznacza, że po dojściu do n=2 przejdziemy kolejno do n=0, potem n=-
2, itd. Nigdy, więc nie znajdzie się przypadek bazowy ( n=1 ), który zatrzyma rekursję.
Wniosek:
Należy zawsze sprawdzać, czy dla wartości parametrów wejściowych
należących do dziedziny wartości, które mogą być użyte, rekurencja kiedyś się
skończy.
NWP - rekurencyjny algorytm Euklidesa
Na zakończenie rozważań o rekurencji omówimy jeden z klasycznych algorytmów
rekurencyjnych, którym jest algorytm Euklidesa obliczający największy wspólny podzielnik
dwu liczb naturalnych.
Definicja
Największym wspólnym podzielnikiem ( ozn. NWP ) dwu liczb całkowitych nazywamy
największą liczbę będącą podzielnikiem ich obu.
Poniższa zależność rekurencyjnia podana przez Euklidesa w IV wieku p.n.e., jest podstawą
obliczenia NWP:
n gdy m mod n = 0
Å„Å‚
NWP(m, n) =
òÅ‚
ółNWP(n, m mod n) gdy m mod n `" 0
gdzie m, n >0.
Przykład:
Obliczyć NWP dla dwóch licz całkowitych: 243 i 114.
Mamy
NWP(243,114)= NWP(114,15)= NWP(15,9)= NWP(9,6)= NWP(6,3)= NWP(3,0)= 3
Postać pseudokodu funkcji EUKLID realizującej NWP :
Funkcja EUKLID(m,n);
{zakładamy, że me"0, ne"0}
poczÄ…tek
jeżeli n=0 wtedy EUKLID:=m
w przeciwnym razie
EUKLID:= EUKLID (n, m mod n)
koniec;
Np. Dla m=30 i n=31 kolejne wywołania funkcji EUKLID sa następujaceL
EUKLID(30,21) EUKLID(21,9) EUKLID(9,3) EUKLID(3,0) = 3
Mamy tu trzy rekurencyjne wywołania funkcji EUKLID. Ciąg wywołań nie może być
nieskończony, gdyż za każdym wywołaniem zmniejsza się wartość drugiego argumentu.
Zatem funkcja EUKLID zawsze się kończy i oblicza poprawny wynik.
Liczba wywołań rekurencyjnych funkcji EUKLID dla m>n>0 wynosi: O(log b).
4. Podstawowe struktury danych
Dane, z którymi pracują algorytmy, są zbiorami, na których dozwolone są pewne operacje.
Rodzaj tych operacji określa wewnętrzna organizacja danego zbioru. Ze względu na to, że
operacje te mogą powiększać, zmniejszać lub zmieniać ich zawartość, zbiory takie nazywamy
zbiorami dynamicznymi.
Operacje wykonywane na zbiorach dynamicznych można podzielić na dwie grupy:
Zapytania  czyli operacje, które pozwalają uzyskać wyłącznie pewne informacje na
temat zbioru
Operacje modyfikujące - czyli operacje, które mogą zmieniać zbiór
Lista typowych operacji na zbiorach dynamicznych:
Oznaczenia: S- zbiór, x - element zbioru S, k- wartość klucza dla elementu zbioru S
SZUKAJ(S,k) Zapytanie, które dla zbioru S oraz wartości klucza k, daje w
wyniku albo element x ze zbioru S, o kluczu równym k, albo NIC,
gdy taki element nie należy do S
DOPISZ(S,x) Operacja modyfikująca, która dodaje element x do zbioru S
USUC
(S,x) Operacja modyfikująca, która usuwa element x ze zbioru S
MINIMUM(S) Zapytanie, które podaje element ze zbioru S o najmniejszej
wartości klucza
MAKSIUM(S) Zapytanie, które podaje element ze zbioru S o największej
wartości klucza
NAST
PNIK(S,x) Zapytanie, które podaje następnik elementu x w zbiorze S lub
NIC, gdy x jest największym w S
POPRZEDNIK(S,x) Zapytanie, które podaje element poprzedzający x w zbiorze S
lub NIC, gdy x jest najmniejszym w S
Uwaga: Dla operacji typu ZAPYTANIE zakładamy, że zbiór S jest liniowo uporządkowany.
Operacja SZUKAJ może być wykonywana również na zbiorze nieuporządkowanym.
A) Listy
Lista jest to skończony ciąg elementów
q=[x1, x2, ... xn],
czyli elementy ułożone w porządku liniowym. Porządek ten określają wskaz
niki zwiÄ…zane z
każdym elementem listy.
Skrajne elementy listy x1 i xn nazywane są końcami listy (xn-lewym, xn-prawym), natomiast
wielkość |q|=n - długością listy (lub rozmiarem listy).
Szczególnym przypadkiem jest lista pusta: q=[] o długości 0.
Niech dane będą dwie listy:
q=[x1, x2,... xn] , r=[y1, y2,... ym] oraz 0d" id" jd" n
Podstawowymi operacjami na listach sÄ…:
- dostęp do elementu listy: q[i]=xi
- podlista q[i..j]=[xi, xi+1,... xj]
- złożenie (konkatenacja) list qr=[x1, ...xn, y1,..., ym]
Obsługa listy ogranicza się do operacji wykonywanych na jej końcach:
a) front(q)=q[1]- pobieranie lewego końca listy
b) push(q,x)=[x]&q - wstawienie elementu x na lewy koniec listy
c) pop(q)=q[2...|q|] - usunięcie bieżącego lewego krańca listy
d) rear(q)=q(|q|) - pobieranie prawego końca listy
e) inject(q,x)= q&[x] - wstawienie elementu x n prawy koniec listy
f) eject(q)= q[1,...,|q|-1] -usunięcie bieżącego prawego końca listy
Do budowy listy używane są dwa typy komórek:
Typ INFO;
- jest komórką informacyjną zawierającą dwa wskaz
niki: do początku i do końca
listy.
Typ ELEMENT
- jest komórką roboczą i zawiera dwa pola:
- wartość elementu
- wskaz
nik do następnego elementu listy
Lewy koniec ??? Wartość
(głowa)
Prawy koniec ??? Gdzie
???
(ogon) następny
Typ Typ ELEMENT
INFO
W zależności od wykazu dozwolonych operacji rozróżniamy różne rodzaje list:
1) lista jednokierunkowa
25 475 3
NIC
głowa
ogon
INFO ELEMENT
x1 x2 .... xn
operacje: front, push, pop
2) lista jednokierunkowa cykliczna
S 125 -42
operacje: front, push, pop, rear, inject
3) lista dwukierunkowa
188125 45
NIC NIC
x1 x2 .... xn
3) lista dwukierunkowa cykliczna
5 8 40 50
x1 x2 .... xn
5) STOS (lista jednokierunkowa)
Dozwolone operacje
- dopisanie elementu od strony wierzchołka stosu PUSH
- usunięcie elementu z wierzchołka stosu POP

Zasada LIFOLast-In-First-Out


Stos pusty push(5) push(15) pop(15)
15
5 5 5
6) Kolejka (lista jednokierunkowa)
Dozwolone operacje
- pobieranie elementu z dołu ( z czoła kolejki )
- dopisanie elementu od strony wierzchołka PUSH
- usunięcie elementu od strony czoła INJECT

Zasada FIFO First -In-First-Out


kolejka pusta push(5) push(15)
15
5 5 15
Inject (5)
B) DRZEWA
Drzewo (ang. tree) jest strukturą podobną do listy jednokierunkowej, z tą różnicą, że każdy
element może mieć dowiązania do więcej niż jednego swojego następnika.
Na przykład:
A
B C D
E F G
H I J
Definicja drzewa (rekurencyjna)
Drzewem nazywamy
- strukturÄ™ pustÄ… (drzewo puste) lub
- węzeł, zwany korzeniem drzewa (ang. root), połączony z zerem lub większą liczbą drzew
zwanych poddrzewami (ang. subtrees)
Podstawowe terminy dotyczÄ…ce drzew:
Korzeń - wyróżniony wierzchołek
Gałąz
- dowolne połączenie pomiędzy węzłami
Liść - węzeł nie mający poddrzew
Węzeł wewnętrzny - węzeł nie będący liściem.
Dla dwóch węzłów połączonych gałęzią zachodzą powiązania:
Węzeł rodzicielski: ten, z którego gałęzi wychodzi
Węzeł potomny: ten, do którego gałęzi wchodzi
Korzeń jest jedynym węzłem, który NIE MA węzła rodzicielskiego.
Rodzic dla B (poprzednik B, ojciec B)
A
B
Potomek A (następnik A, syn A)
Wszystkie węzły leżące na drodze od korzenia do danego węzła nazywane są przodkami
tego ostatniego.
Węzły, dla których dany węzeł pełni rolę przodka nazywane są jego potomkami.
Bezpośredni potomkowie węzła nazywani są jego synami, on zaś nazywany jest ich ojcem.
Pomiędzy węzłami - synami tego samego węzła ojca - istnieje relacja rodzeństwa, a ich określa
się braćmi .
Stopniem węzła nazywamy liczbę jego następników, natomiast stopniem drzewa -
największą liczbę spośród stopni jego węzłów.
Głębokością węzła nazywamy liczbę większą o 1 od liczby jego przodków. Głębokość
drzewa (lub wysokość drzewa) to maksymalna spośród głębokości jego węzłów.
korzeń Głębokość 1
A
B C D Głębokość 2
gałęzie
E F Głębokość 3
H I J liście Głębokość 4
Synowie E: H,I,J
Ojciec F: D (zawsze TYLKO JEDEN)
Bracia : H,I,J
Stopień E : 3
Stopień drzewa : 3
Głębokość F : 3
Głębokość drzewa : : 4
Elementy składowe przykładowego drzewa
Drzewo stopnia 2 nazywane jest często drzewem binarnym. Struktura organizacji
dowolnego wierzchołka takiego drzewa jest następująca:
Adres ojca
Wartość węzła
Adres lewego syna Adres prawego syna
Sposoby przeglądania (odwiedzania) wierzchołków drzewa
Metoda PREORDER
1. odwiedz
korzeń drzewa
2. odwiedz
lewe poddrzewo (jeżeli istnieje) metodą PREORDER
3. odwiedz
prawe poddrzewo (jeżeli istnieje) metodą PREORDER
czyli Korzeń-Lewe-Prawe ( K-L-P)
Metoda INORDER
1. odwiedz
lewe poddrzewo (jeżeli istnieje) metodą INORDER
2. odwiedz
korzeń drzewa
3. odwiedz
prawe poddrzewo (jeżeli istnieje) metodą INORDER
czyli Lewe-Korzeń-Prawe ( L-K-P )
Metoda POSTORDER
1. odwiedz
lewe poddrzewo (jeżeli istnieje) metodą POSTORDER
2. odwiedz
prawe poddrzewo (jeżeli istnieje) metodą POSTORDER
3. odwiedz
korzeń drzewa
czyli Lewe-Prawe-Korzeń ( L-P-K )
Metoda LEVELORDER
1. odwiedz
korzeń drzewa
2. odwiedz
następniki korzenia od lewej do prawej
3. odwiedz
wnuki korzenia od lewej do prawej
4. itd...
Przykład
A
B C
D E F G
PREORDER = A-B-D-E-C-F-G ( K-L-P )
1
2 5
3 4 6 7
INORDER = D-B-E-A-F-C-G ( L-K-P )
4
2 6
1 3 5 7
POSTORDER = D-E-B-F-G-C-A ( L-P-K )
7
3 6
1 2 4 5
LEVELORDER = A-B-C-D-E-F-G
1
2 3
4 5 6 7