Algorytmy i struktury danych
Prowadzący:
dr hab. inż. Kazimierz Worwa, prof. WAT
e-mail:
kworwa@wat.edu.pl
r.a. 2008/2009
WOJSKOWA AKADEMIA TECHNICZNA
Wydział Cybernetyki
2
Algorytmy i struktury danych
A L G O R Y T M Y I ST R U K T U R Y D A N Y C H
R A ZE M
W ykłady
Ć w iczenia
L aboratoria
60
30x
10
20+
3
Algorytmy i struktury danych
Przedmiot kończy się egzaminem
Warunkiem dopuszczenia do egzaminu jest uzyskanie co najmniej 16 pkt.
z ćwiczeń i zajęć laboratoryjnych (łącznie)
W ramach ćwiczeń rachunkowych student może uzyskać do 10 pkt., w tym:
0 – 5 pkt. z odpowiedzi ustnych i/lub sprawdzianów pisemnych,
wg ustaleń prowadzącego ćwiczenia;
0 – 5 pkt. z kolokwium końcowego;
W ramach ćwiczeń laboratoryjnych student może uzyskać do 20 pkt.;
na każdych ćwiczeniach laboratoryjnych student powinien opracować
(napisać
i
uruchomić)
program,
będący
rozwiązaniem
zadania
sformułowanego przez prowadzącego zajęcia; za poprawny, napisany w
trakcie zajęć program student otrzymuje 2 pkt.; za każdy poprawny program
oddany z opóźnieniem (na kolejnych zajęciach) student otrzymuje 1 pkt.
Egzamin - test wielokrotnego wyboru
Warunki zaliczenia przedmiotu
4
Algorytmy i struktury danych
LITERATURA
1.
Aho A.V., Hopcroft J.E., Ullman J.D.: Algorytmy i struktury danych.
Wydawnictwo Helion, Gliwice, 2003.
2. Aho A.V., Hopcroft J.E., Ullman J.D.: Projektowanie i analiza
algorytmów. Wydawnictwo Helion, Gliwice, 2003.
3. Banachowski L., Diks K., Rytter W., Algorytmy i struktury danych.
WNT, Warszawa, 2006.
4. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Wprowadzenie do
algorytmów. WNT, Warszawa, 2005.
5. Drozdek A.: C++. Algorytmy i struktury danych. Wydawnictwo Helion,
Gliwice, 2004.
6. Kotowski P.: Algorytmy + struktury danych = abstrakcyjne typy
danych. Wydawnictwo BTC, Warszawa, 2006.
7. Harris S, Ross J.: Algorytmy od podstaw. Wydawnictwo Helion,
Gliwice, 2006.
8. Wirth N.: Algorytmy + struktury danych = programy. WNT, Warszawa,
2004.
9. Wróblewski P.: Algorytmy, struktury danych i techniki programowania.
Wydawnictwo Helion, Gliwice, 2006.
5
Algorytmy i struktury danych
Tematyka przedmiotu
Poj
ę
cia podstawowe
Listy
Kolejki (LIFO, FIFO, kolejki priorytetowe)
Drzewa binarne
drzewa BST
drzewa AVL
drzewa czerwono-czarne
drzewa cz
ęś
ciowo uporz
ą
dkowane (kopce)
Drzewa wielokierunkowe
Algorytmy sortowania
wewn
ę
trznego
zewn
ę
trznego
Podstawowe algorytmy grafowe
Tablice rozproszone (haszowanie)
Problemy obliczeniowo trudne
6
Algorytmy i struktury danych
Materiały do wykładów
Materiały wykorzystywane na wykładach udost
ę
pniam na stronie
http://www.kw.ocom.pl/
folder
Algorytmy i struktury danych
logowanie:
nazwa u
ż
ytkownika
2008/2009
hasło
sl
Algorytmy i struktury danych
Wykład 1-2
Pojęcia podstawowe.
Złożoność obliczeniowa algorytmów.
8
Algorytmy i struktury danych
Tematyka wykładu
Poj
ę
cia podstawowe
Klasyfikacja algorytmów
Własno
ś
ci algorytmów
Metody oceny algorytmów
Poj
ę
cie zło
ż
ono
ś
ci obliczeniowej algorytmów
Zło
ż
ono
ść
asymptotyczna: O-notacja,
Ω
-notacja,
Θ
-notacja
Wyznaczanie zło
ż
ono
ś
ci czasowej algorytmów:
iteracyjnych
rekurencyjnych
9
Algorytmy i struktury danych
Potoczne rozumienie pojęcia „algorytm”
Algorytmika jest dziedzin
ą
wiedzy zajmuj
ą
c
ą
si
ę
badaniem
algorytmów
Potocznie algorytm jest rozumiany jako pewien przepis na
wykonanie zestawu czynno
ś
ci, prowadz
ą
cych do osi
ą
gni
ę
cia
oczekiwanego i z góry okre
ś
lonego celu
Mówi si
ę
równie
ż
,
ż
e
algorytm jest pewn
ą
ś
ci
ś
le okre
ś
lon
ą
procedur
ą
obliczeniow
ą
, która dla zestawu wła
ś
ciwych danych
wej
ś
ciowych generuje okre
ś
lone dane wyj
ś
ciowe
Dzisiejsze, uogólnione znaczenie słowa algorytm:
zbiór reguł post
ę
powania, umo
ż
liwiaj
ą
cych rozwi
ą
zanie okre
ś
lonego
zadania w sko
ń
czonej liczbie kroków (w sko
ń
czonym czasie)
10
Algorytmy i struktury danych
P
ochodzenie słowa „algorytm”
Słowo „algorytm” pochodzi od łaci
ń
skiego słowa „algorism”,
rozumianego w
ś
redniowieczu jako sztuka rachowania na liczbach
w systemie decymalnym
Słowo „algorism” zostało utworzone od nazwiska perskiego
matematyka z 9-tego wieku n.e., Muhameda ibu-Musy al-Choresmi,
twórcy systemu dziesi
ę
tnego
11
Algorytmy i struktury danych
Pojęciowy model algorytmu
Algorytm mo
ż
e by
ć
rozumiany jako pewne odwzorowanie
f
,
które dla okre
ś
lonego zestawu danych wej
ś
ciowych
We
generuje okre
ś
lony zestaw danych wyj
ś
ciowych
Wy
:
f: We
Wy
Dane
wejściowe
We
Dane
wyjściowe
Wy
f
12
Algorytmy i struktury danych
Pojęcie dziedziny algorytmicznej
Ka
ż
dy algorytm działa na pewnym zbiorze obiektów (np. liczb),
wykonuj
ą
c na tych obiektach pewne operacje
Zbiór obiektów wraz z operacjami wykonywanymi na tych
obiektach nazywamy dziedzin
ą
algorytmiczn
ą
13
Algorytmy i struktury danych
S
posoby zapisu algorytmów
Opis algorytmu obejmuje precyzyjny opis jego kolejnych
kroków
Do przedstawienia algorytmu stosuje si
ę
:
opis werbalny,
zapis formalny, np.:
zapisy graficzne (schematy blokowe),
formalne specyfikacje programów (np.VDM)
zapisy w postaci pseudokodu (paraprogramu)
zapis algorytmu w dowolnym j
ę
zyku programowania
14
Algorytmy i struktury danych
Język programowania
J
ę
zyk programowania jest
ś
rodkiem umo
ż
liwiaj
ą
cym zapis algorytmów w
postaci zrozumiałej dla człowieka, a równocze
ś
nie przetwarzalnej do postaci
zrozumiałej dla komputera.
Zapis algorytmu w j
ę
zyku programowania jest traktowany jako zapis
formalny.
Program komputerowy mo
ż
e by
ć
uznawany za jeden z rodzajów modeli
matematycznych.
Kod źródłowy programu
(w języku programowania)
Kod wynikowy programu
(w języku maszynowym)
Przetworzenie
programu
źródłowego
w kod
maszynowy
15
Algorytmy i struktury danych
Klasyfikacja algorytmów
Rozwa
ż
a
ć
b
ę
dziemy nast
ę
puj
ą
ce klasy algorytmów:
algorytmy sekwencyjne - algorytmy równoległe;
algorytmy numeryczne - algorytmy nienumeryczne;
algorytmy rekurencyjne - algorytmy iteracyjne.
16
Algorytmy i struktury danych
Techniki algorytmiczne
Podstawowe techniki wykorzystywane w budowie algorytmów:
Iteracja
Rekurencja
17
Algorytmy i struktury danych
Rekurencja
Rekurencja oznacza wywołanie funkcji (procedury) przez t
ę
sam
ą
funkcj
ę
(procedur
ę
)
Niepo
żą
dana cecha definicji rekurencyjnych: aby wyznaczy
ć
n-t
ą
warto
ść
trzeba najpierw wyznaczy
ć
wszystkie „wcze
ś
niejsze” warto
ś
ci
Wa
ż
ne jest, aby kolejne wywołania funkcji (procedury) rekurencyjnej
były realizowane dla kolejnych warto
ś
ci parametrów formalnych w taki
sposób, aby nie doszło do zjawiska „niesko
ń
czonej p
ę
tli
rekurencyjnych wywoła
ń
funkcji”
18
Algorytmy i struktury danych
Stos programu w wywołaniach
rekurencyjnych – przykład C/C++
Adres powrotu do
systemu operacyjnego
Dno stosu programu
Adres powrotu z funkcji
Zwracana wartość
Parametry przez adres
Parametry przez wartość
Zmienne lokalne
Adres powrotu z funkcji
Zwracana wartość
Parametry przez adres
Parametry przez wartość
Zmienne lokalne
Adres powrotu z funkcji
Zwracana wartość
Parametry przez adres
Parametry przez wartość
Zmienne lokalne
funkcja main()
funkcja f1
funkcja f2
funkcja fN
Kolejne poziomy rekurencji wymagają
odkładania na stosie programu kolejnych
rekordów aktywacji funkcji
.
.
.
Stos programu w wywołaniach
rekurencyjnych jest bardziej
eksploatowany niż wtedy, gdy wywołania
nie są rekurencyjne
19
Algorytmy i struktury danych
Funkcja rekurencyjna – ciąg Fibonacciego
n-ty wyraz ci
ą
gu Fibonacciego jest wyliczany wg formuły, n
≥
0:
n
dla n<2
Fib(n)=
Fib(n-2) + Fib(n-1) dla n>=2
Rekurencyjna implementacja w j
ę
zyku C:
long int Fib (int n)
{
if (n<2)
return n;
else
return Fib(n-2) + Fib (n-1);
}
Dla dużych n stos programu
„nie wytrzyma” takiej realizacji
funkcji Fib!
20
Algorytmy i struktury danych
Efektywność rekurencyjnego wykonania funkcji
Fibonacciego (cd.)
Rekurencyjna implementacja funkcji Fibonacciego jest bardzo nieefektywna.
Stos programu nie jest praktycznie w stanie zrealizowa
ć
tego algorytmu ju
ż
dla liczb wi
ę
kszych od 50.
Oznacza to,
ż
e program ma zbyt du
żą
„zło
ż
ono
ść
pami
ę
ciow
ą
”.
F(6)
F(5)
F(4)
F(2)
F(0)
F(1)
F(3)
F(1)
F(2)
F(3)
F(1)
F(2)
F(4)
F(2)
F(3)
F(0)
F(1)
F(0)
F(1)
F(0)
F(1)
F(1)
F(2)
F(0)
F(1)
0
1
0
1
1
0
1
0
1
0
1
1
1
Przykład: drzewo wywoła
ń
dla F(6):
21
Algorytmy i struktury danych
Efektywność rekurencyjnego wykonania funkcji Fibonacciego
2 692 537
1 346 268
30
242 785
121 392
25
21 891
10 945
20
1 973
986
15
177
88
10
25
12
6
Liczba
wywoła
ń
Liczba
dodawa
ń
n
22
Algorytmy i struktury danych
Iteracyjne wykonanie rekurencyjnej funkcji
Fibonacciego
Bardziej efektywna jest iteracyjna implementacja funkcji Fibonacciego. Nie
przepełniamy wtedy stosu programu i wykonujemy znacznie mniejsz
ą
liczb
ę
przypisa
ń
warto
ś
ci ni
ż
w implementacji rekurencyjnej
Przykład iteracyjnej implementacji funkcji Fibonacciego:
long int IteracyjnyFib(int n)
{
register int i=2, last=0, tmp; long int current =1;
if (n<2)
return n;
else {
for ( ; i<=n; i++) {
tmp = current;
current += last;
last = tmp;
}
return current;
}
}
23
Algorytmy i struktury danych
Efektywność iteracyjnego wykonania rekurencyjnej funkcji
Fibonacciego
2 692 537
87
30
242 785
72
25
21 891
57
20
1 973
42
15
177
27
10
25
15
6
Liczba przypisa
ń
(wywoła
ń
) w algorytmie
rekurencyjnym
Liczba przypisa
ń
w
algorytmie iteracyjnym
n
Program 1.1b
Program 1.1a
24
Algorytmy i struktury danych
Pułapki rekurencji
int jakas_funkcja(int n)
{
if (n==1)
return 1;
else
if ((n%2)==0)
// czy n jest parzyste?
return jakas_funkcja(n-2)*n;
else
return jakas_funkcja(n-1)*n;
}
Program 1.2
Co będzie wynikiem wykonania poniższej funkcji?
25
Algorytmy i struktury danych
Jak porównywać algorytmy?
Idealny algorytm to taki, który:
ma czytelny i zrozumiały kod,
jest napisany w ogólnie dostępnym języku programowania,
jest efektywny obliczeniowo (szybko liczy, nie wymaga dużej pamięci),
zawsze daje poprawne wyniki.
26
Algorytmy i struktury danych
Jak porównywać algorytmy – przykładowe kryteria
prostota,
czytelność kodu,
długość kodu,
poprawność,
czas realizacji (obliczeń),
zajętość pamięci.
27
Algorytmy i struktury danych
Częściowa poprawność algorytmu
Specyfikacją algorytmu nazywamy parę warunków (własności):
Warunek początkowy
Warunek końcowy
< wp , wk >
Algorytm A wykorzystujący strukturę danych S jest częściowo poprawny ze
względu na specyfikację <wp, wk>, jeżeli dla wszystkich danych spełniających
warunek początkowy i dla których algorytm zatrzyma się, uzyskane wyniki
spełniają warunek końcowy.
wk
wp
A
28
Algorytmy i struktury danych
Całkowita poprawność algorytmu
wk
wp
A
Mówimy, że algorytm A wykorzystujący strukturę danych S jest całkowicie
poprawny ze względu na specyfikację <wp, wk> jeżeli dla wszystkich
danych w strukturze S spełniających warunek początkowy wp, algorytm
zatrzymuje się i daje wyniki spełniające warunek końcowy wk.
29
Algorytmy i struktury danych
Złożoność obliczeniowa - miara służąca do porównywania efektywności
algorytmów. Mamy dwa zasadnicze kryteria efektywności: czas i pamięć.
Do oceny efektywności stosujemy jednostki logiczne, wyrażające
związek miedzy rozmiarem danych n (np. wielkość pliku lub tablicy)
a ilością czasu T potrzebną na ich przetworzenie.
Złożoność obliczeniowa algorytmów
30
Algorytmy i struktury danych
Rodzaje złożoności obliczeniowej algorytmów
Zło
ż
ono
ść
pami
ę
ciowa - wyra
ż
ana w skali zaj
ę
to
ś
ci pami
ę
ci (PAO,
pami
ę
ci zewn
ę
trznej), niezb
ę
dnej dla realizacji algorytmu
Zło
ż
ono
ść
czasowa - wyra
ż
ana w skali czasu wykonania algorytmu
(liczba kroków, czas rzeczywisty)
Na ogół (obecnie) zło
ż
ono
ść
czasowa jest wa
ż
niejsza od zło
ż
ono
ś
ci
pami
ę
ciowej
31
Algorytmy i struktury danych
Czynniki wpływające na czas wykonania programu
Rozmiar danych wej
ś
ciowych algorytmu
Jako
ść
kodu wynikowego generowanego przez kompilator (j
ę
zyk
kodu
ź
ródłowego)
Architektura i szybko
ść
komputera, na którym program jest
wykonywany
Efektywno
ść
wykorzystanego algorytmu (jego zło
ż
ono
ść
czasowa)
32
Algorytmy i struktury danych
Złożoność czasowa algorytmu
Definicja
Zło
ż
ono
ść
czasowa to liczba operacji podstawowych, wykonanych
przez algorytm w czasie jego realizacji, wyra
ż
ona jako funkcja rozmiaru
danych.
Oznaczenie
Zło
ż
ono
ść
czasowa algorytmu A jako funkcja rozmiaru danych n:
lub
33
Algorytmy i struktury danych
Złożoność czasowa algorytmu
Do oszacowania czasu realizacji algorytmu nie powinno si
ę
u
ż
ywa
ć
zwykłych jednostek czasu
Zamiast tego powinny by
ć
stosowane jednostki logiczne, okre
ś
laj
ą
ce
zwi
ą
zek mi
ę
dzy rozmiarem danych wej
ś
ciowych a czasem
potrzebnym na ich przetworzenie
Funkcje opisuj
ą
ce zwi
ą
zek mi
ę
dzy
T(n)
a
n
mog
ą
by
ć
bardzo zło
ż
one;
w praktyce upraszczamy je, pozostawiaj
ą
c tzw. składowe dominuj
ą
ce,
tj. składowe maj
ą
ce najwi
ę
kszy wpływ na warto
ś
ci
T(n)
34
Algorytmy i struktury danych
Przykład
Niech zale
ż
no
ść
czasu realizacji algorytmu od rozmiaru
danych wej
ś
ciowych opisuje funkcja
f(n) = n
2
+ 100n + log
10
n + 1000
35
Algorytmy i struktury danych
Porównanie szybkości wzrostu funkcji
f(n)= log n
f(n)=n
f(n) = 2
n
f(n) = n
2
n
f(n)
36
Algorytmy i struktury danych
Funkcja: f(n) = n
2
+ 100*n + log
10
n + 1000
n f(n) n
2
100*n log
10
n 1000
1
1 101 0.1% 9% 0.0 % 91%
10 2 101 4.8% 48% 0.05% 48%
100 21 002 48% 48% 0.001% 4.8%
10
3
1 101 003 91% 9% 0.0003%
0.09%
10
4
99% 1% 0.0%
0.001%
10
5
99,9% 0.1% 0.0%
0.0000%
Szybkość wzrostu poszczególnych składników funkcji
Dla dużych wartości n składnikiem dominującym jest n
2
, tzn. funkcja rośnie
jak n
2
; pozostałe składniki mogą być pominięte;
n – ilość wykonywanych operacji
37
Algorytmy i struktury danych
Funkcja wyrażająca zależność miedzy n a T jest zwykle bardzo
skomplikowana, a jej dokładne obliczenie ma znaczenie jedynie w
odniesieniu do specyficznych problemów
Przybliżoną miarą efektywności najczęściej stosowaną w praktyce jest tzw.
asymptotyczna złożoność obliczeniowa.
Asymptotyczna złożoność obliczeniowa
38
Algorytmy i struktury danych
O-notacja
Definicja:
Funkcja
f(n)
jest funkcj
ą
o zło
ż
ono
ś
ci
O(g(n)),
je
ż
eli istniej
ą
takie
liczby dodatnie
c
i
n
o
,
ż
e dla ka
ż
dego
zachodzi
Zgodnie z powy
ż
sz
ą
definicj
ą
, zwi
ą
zek mi
ę
dzy funkcjami
f
i
g
mo
ż
na wyrazi
ć
stwierdzaj
ą
c,
ż
e
g(n)
jest kresem górnym dla
f(n)
Uwaga
: powy
ż
sza definicja nie daje
ż
adnych wskazówek co do
tego, jak wyznaczy
ć
stałe
c
i
n
0
(takich par mo
ż
e by
ć
wiele)
Interpretacja:
O(g(n)) = { f(n): istniej
ą
dodatnie liczby c i n
0
takie,
ż
e dla
ka
ż
dego n
≥
n
0
zachodzi 0
≤
f(n)
≤
c g(n) }
Piszemy: f(n)
∈
O(g(n)) lub cz
ęś
ciej f(n) = O(g(n))
0
n
n
≥
g(n)
c
f(n)
≤
39
Algorytmy i struktury danych
O-notacja – ilustracja graficzna
f(n)
c g(n)
n
n
0
f
(n)=O(g(n))
40
Algorytmy i struktury danych
Przykład
Niech zale
ż
no
ść
czasu realizacji algorytmu od rozmiaru
danych wej
ś
ciowych n opisuje funkcja
f(n) = n
2
+ 100n + log n + 1000
Wówczas, wykorzystuj
ą
c O-notacj
ę
, mo
ż
na napisa
ć
,
ż
e
n
2
+ 100n + log n + 1000
∈
O(n
2 )
Zatem, dla badanej funkcji
T(n) = n
2
Tak okre
ś
lona zło
ż
ono
ść
czasow
ą
algorytmu nazywa si
ę
asymptotyczn
ą
zło
ż
ono
ś
ci
ą
czasow
ą
W praktyce wykorzystuje si
ę
tak
ż
e poj
ę
cia optymistycznej,
pesymistycznej oraz
ś
redniej zło
ż
ono
ś
ci czasowej algorytmu
41
Algorytmy i struktury danych
Własności O-notacji
Własność 1 (przechodniość)
Jeśli f(n) jest O(g(n)) i g(n) jest O(h(n)), to f(n) jest O(h(n)).
Własność 2:
Jeśli f(n) jest O(h(n)) i g(n) jest O(h(n)), to f(n)+g(n) jest O(h(n)).
Własność 3:
Funkcja an
k
jest O(n
k
).
Własność 4:
Funkcja n
k
jest O(n
k+j
) dla dowolnego nieujemnego j.
Z powyższych własności wynika, ze dowolny wielomian jest „wielkie O” dla n
podniesionego do najwyższej w nim potęgi, czyli
f(n) = a
k
n
k
+ a
k-1
n
k-1
+ ... + a
1
n
+a
0
jest O(n
k
)
(jest też oczywiście O(n
k+j
) dla dowolnego nieujemnego j).
42
Algorytmy i struktury danych
Własność 5:
Jeśli f(n)=c g(n), to f(n) jest O(g(n))
Własność 6:
Funkcja log
a
n jest O(log
b
n) dla dowolnych a i b większych niż 1
Własność 7:
log
a
n jest O(log
2
n) dla dowolnego dodatniego a
Własności O-notacji (cd.)
Wniosek:
Wszystkie funkcje logarytmiczne (niezależnie od podstawy logarytmu) są
sobie równoważne w sensie O-notacji
43
Algorytmy i struktury danych
Własności O-notacji (cd.)
Własność 8 (reguła sumy)
Je
ś
li
T
1
(n)=O(f(n))
i
T
2
(n)=O(g(n))
s
ą
czasami wykonywania dwóch
fragmentów algorytmu, to ł
ą
czny czas wykonania obydwu fragmentów
wynosi:
T
1
(n) +T
2
(n) = O(max{ f(n), g(n)})
Własność 9 (reguła iloczynu)
Niech
T
1
(n)=O(f(n))
i
T
2
(n)=O(g(n))
s
ą
czasami wykonywania dwóch
fragmentów algorytmu. Wówczas:
T
1
(n)
⋅
T
2
(n) = O(f(n)
⋅
g(n))
44
Algorytmy i struktury danych
Jedną z najważniejszych funkcji przy ocenianiu efektywności algorytmów
jest funkcja logarytmiczna.
Jeżeli można wykazać, że złożoność algorytmu jest rzędu logarytmicznego,
algorytm można traktować jako bardzo dobry.
Istnieje wiele funkcji lepszych w tym sensie niż logarytmiczna, jednak
zaledwie kilka spośród nich, jak O(log
2
log
2
n) czy O(1) ma praktyczne
znaczenie.
Własności O-notacji
45
Algorytmy i struktury danych
Ω
Ω
Ω
Ω
- notacja
O-notacja dotyczy kresu górnego funkcji
Istnieje symetryczna definicja kresu dolnego w postaci
Ω
-notacji
Definicja:
f(n)
jest funkcj
ą
o zło
ż
ono
ś
ci
je
ż
eli istniej
ą
takie liczby
dodatnie
c
i
n
0
,
ż
e dla ka
ż
dego
zachodzi
Wniosek
Funkcja f(n)
ma zło
ż
ono
ść
wtedy i tylko wtedy, gdy
g(n)
ma zło
ż
ono
ść
0
n
n
≥
g(n)
c
f(n)
≥
(g(n))
Ω
(f(n))
O
(g(n))
Ω
46
Algorytmy i struktury danych
Ω
Ω
Ω
Ω
- notacja
Interpretacja:
Ω
(g(n)) = { f(n): istniej
ą
dodatnie liczby c i n
0
takie,
ż
e dla
ka
ż
dego n
≥
n
0
zachodzi 0
≤
c g(n)
≤
f(n) }
Piszemy: f(n)
∈ Ω
(g(n)) lub cz
ęś
ciej f(n) =
Ω
(g(n))
47
Algorytmy i struktury danych
Ω
Ω
Ω
Ω
-notacja – ilustracja graficzna
f(n)
c g(n)
n
n
0
f(n)=
Ω
(g(n))
48
Algorytmy i struktury danych
Θ
Θ
Θ
Θ
- notacja
Definicja
f(n)
jest funkcj
ą
o zło
ż
ono
ś
ci
je
ż
eli istniej
ą
liczby dodatnie
c
1
, c
2
i
n
0
takie,
ż
e dla ka
ż
dego
zachodzi
Wniosek
Funkcja
f(n)
ma zło
ż
ono
ść
wtedy i tylko wtedy, gdy
f(n)
ma zło
ż
ono
ść
i
f(n)
ma zło
ż
ono
ść
(g(n))
Θ
0
n
n
≥
g(n)
c
f(n)
g(n)
c
2
1
≤
≤
(g(n))
Θ
(g(n))
O
(g(n))
Ω
49
Algorytmy i struktury danych
Θ
Θ
Θ
Θ
- notacja
Interpretacja:
Θ
(g(n)) = { f(n): istniej
ą
dodatnie liczby c
1
, c
2
i n
0
takie,
ż
e dla
ka
ż
dego n
≥
n
0
zachodzi 0
≤
c
1
g(n)
≤
f(n)
≤
c
2
g(n) }
Piszemy: f(n)
∈ Θ
(g(n)) lub cz
ęś
ciej f(n) =
Θ
(g(n))
50
Algorytmy i struktury danych
Θ
Θ
Θ
Θ
-notacja – ilustracja graficzna
c
1
g(n)
f(n)=
Θ
(g(n))
f(n)
n
c
2
g(n)
n
0
51
Algorytmy i struktury danych
O-notacja,
Ω
Ω
Ω
Ω
-notacja,
Θ
Θ
Θ
Θ
-notacja – porównanie
f(n)
c g(n)
n
n
0
f(n)=
Ω
(g(n))
f(n)
c g(n)
n
n
0
f
(n)=O(g(n))
c
1
g(n)
f(n)=
Θ
(g(n))
f(n)
n
c
2
g(n)
n
0
52
Algorytmy i struktury danych
Notacja asymptotyczna - podsumowanie
Niech f , g : N
→
R
+
.
Mówimy, że funkcja f jest co najwyżej rzędu g, jeśli
(
∃
c>0,
∃
n
o
∈
N)
∀
n>n
o
f(n)
≤
c g(n)
Mówimy, że funkcja f jest co najmniej rzędu g, jeśli
(
∃
c>0,
∃
n
o
∈
N)
∀
n>n
o
c g(n)
≤
f(n)
f =
Ω
Ω
Ω
Ω
(g )
f = O (g )
f =
Θ
Θ
Θ
Θ
(g )
Mówimy, że funkcja f jest rzędu g, jeśli
(
∃
c
1
>0, c
2
>0,
∃
n
o
∈
N)
∀
n>n
o
c
1
g(n)
≤
f(n)
≤
c
2
g(n)
53
Algorytmy i struktury danych
Porównanie szybkości wzrostu funkcji
Mówimy, że algorytm A ma złożoność czasową:
logarytmiczną
jeśli T(A, n) =
Θ
(log n)
liniową
jeśli T(A, n) =
Θ
(n)
kwadratową
jeśli T(A, n) =
Θ
(n
2
)
wielomianową
jeśli T(A, n) =
Θ
(n
α
)
α ∈
N
wykładniczą
jeśli T(A, n) =
Θ
(a
n
) a
∈
R
+
54
Algorytmy i struktury danych
Porównywanie rzędów funkcji
Przykład 1
Niech f(n)=100n, g(n)= 2n+100, h(n) = 0.1 n
2
+n
Mamy: f = O(n), f =
Ω
(n), g = O(n) ale także g = O(n
2
), g =
Θ
(n)
h = O(n
2
), h
≠
O(n), h =
Ω
(n)
Lemat (o porównywaniu rz
ę
dów funkcji)
Niech lim
n
→∞
→∞
→∞
→∞
f(n)/g(n) = c. Wówczas:
1. Je
ż
eli c
≠≠≠≠
0 to f i g s
ą
tego samego rz
ę
du.
2. Je
ż
eli c = 0, to f = O(g) oraz f
≠≠≠≠ Ω
Ω
Ω
Ω
(g).
3. Je
ż
eli c =+
∞
∞
∞
∞
, to f ma rz
ą
d wi
ę
kszy ni
ż
g,
g = O(f) i g
≠≠≠≠ Ω
Ω
Ω
Ω
(f).
Przykład 2
f(n) = 0,3 n
3
+ 10n + 100
g(n)= n
3
h(n) = log n
lim
n
→∞
f(n)/g(n)= 0,3
Zatem f = g =
Θ
(n
3
)
lim
n
→∞
f(n)/h(n) = +
∞
Zatem h = O(f) = O(n
3
),
h
≠ Ω
(f).
55
Algorytmy i struktury danych
Złożoność a rozmiar i czas
Jaki jest maksymalny rozmiar problemu n, który można rozwiązać w
ustalonym czasie, znając złożoność algorytmu?
Ile czasu potrzeba na rozwiązanie zadania o ustalonym rozmiarze i złożoności?
1 s
1 godz.
n
3
lg n
n
n lg n
n
2
2
n
10
2
15* 10
2
2
1000000
63*10
3
10
6
10
3
19
36*10
8
13* 10
7
60* 10
3
31
T(A,n)
czas
n=10
2
n= 10
4
n
3
lg n
n
n lg n
n
2
2
n
1s
1
1
dni
6.6
µ
s
13.3
µ
s
0.6ms
0.1ms
10ms
10
6
lat
10ms
0.1s
100s
10
100
lat
T(A,n)
wymiar
56
Algorytmy i struktury danych
Czy szybkość może przezwyciężyć złożoność?
Mamy 5 algorytmów A
1
, A
2
, A
3
, A
4
, A
5
rozwiązujących ten sam problem.
Niech s
i
oznacza maksymalny rozmiar problemu, który można rozwiązać na
komputerze 1 przy pomocy algorytmu A
i
w ustalonym czasie t.
Jaki jest maksymalny rozmiar problemu, który można rozwiązać w tym
samym czasie t na komputerze 2, który jest 10 razy szybszy?
Komputer 1
Komputer 2
n
3
lg n
n
n
2
2
n
s
4
2*s
4
s
1
s
1
10
s
2
s
3
s
5
10*s
2
√
10*s
3
3,2 + s
5
5
5
s
x
x
s
2
10
2
2
t
2
10
t
⋅
=
=
⋅
=
Zatem:
czyli
x = 3,2 + s
5
t
)
x
,
A
(
T
=
Szukamy takiego x, że
10
/
t
2
)
s
,
A
(
T
5
s
5
=
=
Dla komputera 2:
t
2
)
s
,
A
(
T
5
s
5
=
=
Dla komputera 1:
57
Algorytmy i struktury danych
Wpływ dziesięciokrotnego przyspieszenia
komputera na wzrost rozmiaru zadania
1,3
13
10
2
n
2,3
27
12
n
3
/2
3,2
45
14
5n
2
10,0
100
10
100n
Wzgl
ę
dny przyrost
rozmiaru problemu
Komputer
dziesi
ę
ciokrotnie
szybszy
Komputer
oryginalny
Zło
ż
ono
ść
czasowa T(n)
58
Algorytmy i struktury danych
Wyznaczanie złożoności czasowej - przykłady
Przykład 1
Pojedyncza pętla wyznaczająca sumę elementów wektora
for (i=sum=0; i<n; i++)
sum=sum+ a[i];
Liczba przypisań w całej pętli: 2+2n
Złożoność czasowa: T(n)=O(n)
59
Algorytmy i struktury danych
Wyznaczanie złożoności czasowej - przykłady
Przykład 2
Pętla podwójna wyznaczająca sumę elementów tablicy
for (i=0; i<n; i++) {
for (j=1, sum=a[0]; j<=i; j++)
sum=sum+ a[j];
printf(„\n Suma podtablicy %d” , sum)
}
Liczba przypisań w całej pętli:
Złożoność czasowa: T(n)=O(n
2
)
)
n
(
O
)
1
n
(
n
n
3
1
)
1
n
...
2
1
(
2
n
3
1
i
2
n
3
1
2
1
n
1
i
=
−
+
+
=
−
+
+
+
+
+
=
+
+
∑
−
=
60
Algorytmy i struktury danych
Wyznaczanie złożoności czasowej - przykłady
Przykład 3
Z
erowanie elementów tablicy leżących na i pod główną przekątną
int tab[n][n];
void zerowanie();
{
int i,j;
i=0;
// 1
while (i<n)
// 1
{
j=0;
// 1
while (j<=i)
// 1
{
tab[i][j]=0; // 1
j=j+1;
// 1
}
i=i+1;
// 1
}
}
Złożoność czasowa (z uwagi na wszystkie instrukcje):
)
n
(
O
2
)
1
n
(
n
3
n
3
1
))
1
i
(
3
3
(
1
)
3
3
(
1
)
n
(
T
2
1
n
0
i
i
0
j
1
n
0
i
=
+
+
+
=
=
+
+
+
=
+
+
=
=
∑
∑
∑
−
=
=
−
=
61
Algorytmy i struktury danych
Kiedy algorytm zawiera rekurencyjne wywołanie samego siebie, jego czas
działania można często opisać zależnością rekurencyjną (rekurencją),
wyrażającą czas dla problemu rozmiaru n za pomocą czasów dla
podproblemów mniejszych rozmiarów.
Możemy więc użyć narzędzi matematycznych, aby rozwiązać rekurencję
i w ten sposób otrzymać oszacowania czasu działania algorytmu.
Złożoność czasowa algorytmów rekurencyjnych
62
Algorytmy i struktury danych
Rekurencja odpowiadającą czasowi działania algorytmu typu “dziel
i zwyciężaj” opiera się na podziale jednego poziomu rekursji na trzy etapy
Niech
T(n)
będzie czasem działania algorytmu dla problemu rozmiaru
n
Jeśli rozmiar problemu jest odpowiednio mały, powiedzmy
n
≤≤≤≤
c
dla pewnej
stałej
c
, to jego rozwiązanie zajmuje stały czas, co zapiszemy jako
Θ
Θ
Θ
Θ
(1)
Załóżmy ze dzielimy problem rozmiaru
n
na
a
podproblemów, każdy rozmiaru
n/b
Jeśli
D(n)
jest czasem dzielenia problemu na podproblemy, a
C(n)
czasem
scalania rozwiązań poszczególnych podproblemów w pełne rozwiązanie
problemu wyjściowego , to otrzymujemy rekurencję
Rekurencja dla algorytmu typu “dziel i zwycieżaj”
c
n
dla
c
n
dla
C(n)
D(n)
aT(n/b)
)
1
(
)
n
(
T
>
≤
+
+
Θ
=
63
Algorytmy i struktury danych
Przykład: algorytm sortowania przez scalanie
znajdujemy środek przedziału, zajmuje to czas stały D(n)=
Θ
(1)
rozwiązujemy rekurencyjnie dwa podproblemy, każdy rozmiaru
n/2, co daje czas działania 2 T(n/2)
łączymy dwa uporządkowane podciągi w jeden (uporzadkowany) w czasie
Θ
(n), a wiec C(n)=
Θ
(n).
Ostatecznie
Można pokazać, że rozwiązaniem tej rekurencji jest T(n) =
Θ
Θ
Θ
Θ
(n log n)
Rekurencja dla algorytmu typu “dziel i zwycieżaj”
1
n
dla
1
n
dla
(n)
)
1
(
2T(n/2)
)
1
(
)
n
(
T
>
=
Θ
+
Θ
+
Θ
=
64
Algorytmy i struktury danych
Metody rozwiązywania rekurencji:
1.
Metoda podstawiania: zgadujemy oszacowanie, a następnie
wykorzystujemy indukcję matematyczną.
2.
Metoda iteracyjna: przekształcamy rekurencję na sumę (korzystamy
z technik ograniczania sum).
3.
Metoda drzewa rekursji: uzupełniająca metodę podstawiania
4.
Metoda rekurencji uniwersalnej: stosujemy oszacowanie na rekurencje
mające postać
T(n) = a T(n/b) + f(n),
gdzie a
≥
1, b>1, a f(n) jest daną funkcją.
Wyznaczanie złożoności czasowej algorytmów rekurencyjnych
65
Algorytmy i struktury danych
Metoda podstawiania:
Polega na odgadnięciu postaci rozwiązania, a następnie wykazaniu przez
indukcję, że jest ono poprawne.
Trzeba także znaleźć wartości odpowiednich stałych.
Metoda jest bardzo skuteczna, ale może być stosowana tylko w przypadkach,
kiedy można przewidzieć postać rozwiązania.
Wyznaczanie złożoności czasowej algorytmów rekurencyjnych
66
Algorytmy i struktury danych
Przykład:
Postać rekurencji: T(n) = 2T(
n/2
) + n
Zachodzi: T(1)=1; T(2)=4; T(3)=5, T(4)=12 ...
Przewidywane rozwiązanie: T(n) = O(n lg n), tzn.
T(n)
≤
c n lg n
Założenie: dla n =
n/2
zachodzi: T(
n/2
)
≤
c
n/2
lg (
n/2
)
Indukcja: T(n)
≤
2[c
n/2
lg (
n/2
)] + n
≤
c n lg(n/2) + n
=
=
c n lg n – c n lg 2 + n
=
c n lg n – cn + n
≤
c n lg n
Zatem, jeśli c
≥≥≥≥
1 zachodzi:
T(n)
≤≤≤≤
c n lg n
Rozwiązanie T(n) = O(n lg n) jest poprawne dla c
≥
2 i n
≥
2
Metoda podstawiania
Dlaczego?
Oznaczenia:
a
- największa liczba całkowita x taka, że x<a
a
- najmniejsza liczba całkowita x taka, że x>a
0
c
>
∃
Dlaczego?
67
Algorytmy i struktury danych
Metoda iteracyjna
Polega na rozwijaniu (iterowaniu) rekurencji i wyrażanie jej jako sumy
składników zależnych tylko od warunków brzegowych.
Następnie mogą być użyte techniki sumowania do oszacowania rozwiązania.
Metoda iteracyjna
68
Algorytmy i struktury danych
Rozwinięcie rekurencji
Jest uproszczoną wersją metody iteracyjnej
Polega na:
rozpisaniu równania rekurencyjnego dla kolejnych wartości
n
,
dodaniu otrzymanych równań stronami,
zredukowaniu jednakowych wyrazów i przekształceniu otrzymanej
zależności tak, aby uzyskać jawną zależność funkcji
T(n)
od
n
Metoda jest skuteczna jedynie w odniesieniu do niektórych postaci rekurencji
Wyznaczanie złożoności czasowej algorytmów rekurencyjnych
69
Algorytmy i struktury danych
Metoda iteracyjna – rozwinięcie rekurencji
Przykład 1.
Funkcja Silnia
int Silnia(int n) {
if (n==0)
return 1;
else
return n*silnia(n-1);
}
≥
+
−
=
=
1
n
dla
1
)
1
n
(
T
0
n
dla
1
)
n
(
T
Zło
ż
ono
ść
czasowa
:
Czas wykonania jednej instrukcji
porównania wartości (ogólnie:
Θ
Θ
Θ
Θ
(1)
70
Algorytmy i struktury danych
1
)
0
(
T
1
)
0
(
T
)
1
(
T
...
1
)
2
n
(
T
)
1
n
(
T
1
)
1
n
(
T
)
n
(
T
=
+
=
+
−
=
−
+
−
=
)
0
(
T
)
1
(
T
...
)
1
n
(
T
1
n
)
0
(
T
)
1
(
T
...
)
1
n
(
T
)
n
(
T
+
+
+
−
+
+
=
+
+
+
−
+
Zatem:
T(n)= n+1=O(n)
Metoda iteracyjna - rozwinięcie rekurencji
≥
+
−
=
=
1
n
dla
1
)
1
n
(
T
0
n
dla
1
)
n
(
T
Przykład 1 (cd.)
dodajemy stronami
71
Algorytmy i struktury danych
Przykład 2:
Postać rekurencji: T(n) = 3T(n/4) + n; T(1)=a
Iterujemy: T(n) = n + 3T(n/4) =
= n + 3[n/4 +3T(n/16)] =
= n + 3 n/4 + 9T( n/16) =
= n + 3 n/4 + 9[ n/16 + 3T(n/16)] =
= n + 3 n/4 + 9 n/16 + 27 T(n/64) = ...
Metoda iteracyjna
)
n
(
)
4
3
(
n
4
n
3
...
4
n
3
4
n
3
4
n
3
n
T(n)
n
log
0
k
k
n
log
n
log
3
3
2
2
4
4
4
Θ
=
=
+
+
+
+
+
≤
∑
=
Iterujemy tak długo, aż osiągniemy warunek brzegowy:
i-ty składnik ciągu wynosi 3
i
n/4
i
Iterowanie kończymy, gdy n/4
i
= 1, czyli i = log
4
n
1
q
,
q
1
q
1
a
S
k
1
k
≠
−
−
=
72
Algorytmy i struktury danych
Drzewo rekursji pozwala w dogodny sposób zilustrować rozwijanie
rekurencji, jak również ułatwia stosowanie aparatu algebraicznego, służącego
do rozwiązywania tej rekurencji
Szczególnie użyteczne gdy rekurencja opisuje algorytm typu “dziel
i zwyciężaj
”
Każdy węzeł drzewa reprezentuje czas wykonania podproblemu
Sumując czasy na kolejnych poziomach drzewa otrzymujemy czas łączny
Drzewo rekursji może stanowić pomoc przy odgadywaniu rozwiązania
(w metodzie podstawienia)
Metoda drzewa rekursji
73
Algorytmy i struktury danych
T(n) = 2 T(n/2) + n
2
, T(1)=a
n
2
T(n/2)
T(n/2)
T(n) =
Θ
(n
2
)
Zatem, ostateczny wynik:
n
2
T(n/4)
T(n/4)
(n/2)
2
(n/2)
2
T(n/4)
T(n/4)
n
2
n
2
/2
n
2
/4
w sumie:
Θ
Θ
Θ
Θ
(n
2
)
Drzewo rekursji
Przykład 1
...
Jaką maksymalną wysokość ma drzewo rekursji?
...
74
Algorytmy i struktury danych
T(n) =
Θ
(n log n )
Zatem, ostateczny wynik:
T(n) = T(n/3) + T(2n/3) + n, T(1)=a
n
n/9
2n/9
n/3
2n/3
2n/9
4n/9
log
3/2
n
wysokość drzewa: log
3/2
n
Drzewo rekursji
Przykład 2
Dlaczego?
w sumie:
n
⋅
log
3/2
n
n
n
n
...
75
Algorytmy i struktury danych
Metoda rekurencji uniwersalnej
Metoda rekurencji uniwersalnej podaje “uniwersalny przepis” rozwiązywania
równania rekurencyjnego postaci
T(n) = a T(n/b) + f(n)
gdzie a
≥
1 i b>1 są stałymi, a f(n) jest funkcją asymptotycznie dodatnią.
Za wartość n/b przyjmujemy najbliższą liczbę całkowitą (mniejszą lub
większą od wartości dokładnej) tj. n/b =n/b lub n/b = n/b
76
Algorytmy i struktury danych
Rekurencja opisuje czas działania algorytmu, który dzieli problem
rozmiaru
n
na
a
problemów, każdy rozmiaru
n/b
, gdzie
a
i
b
są
dodatnimi stałymi.
Każdy z
a
problemów składowych jest rozwiązywany rekurencyjnie
w czasie
T(n/b)
.
Koszt dzielenia problemu oraz łączenia rezultatów częściowych jest
opisany funkcją
f(n)
Dowód twierdzenia o rekurencji uniwersalnej:
patrz: T.H. Cormen, Ch.E.Leiserson, R.L.Rivest , C Stein: Wprowadzenie do algorytmów
Metoda rekurencji uniwersalnej
77
Algorytmy i struktury danych
Niech
a
≥
1
i
b>1
będą stałymi, niech
f(n)
będzie pewną funkcją i niech
T(n)
będzie zdefiniowane rekurencyjnie, dla nieujemnych liczb całkowitych:
T(n) = a T(n/b) + f(n),
gdzie
n/b
oznacza najbliższą liczbę naturalną (mniejszą lub większą od
wartości dokładnej) tj.
n/b =n/b
lub
n/b = n/b
Wtedy funkcja
T(n)
może być ograniczona asymptotycznie w następujący
sposób:
1. Jeśli
dla pewnej stałej
ε
>0
, to
2. Jeśli to
3. Jeśli
dla pewnej stałej
ε
>0
i jeśli
a f(n/b)
≤≤≤≤
c f(n)
dla pewnej stałej
c<1
i wszystkich dostatecznie dużych
n
, to
T(n) =
Θ
Θ
Θ
Θ
(f(n))
Metoda rekurencji uniwersalnej
)
n
(
)
n
(
T
a
log
b
Θ
=
)
n
(
O
)
n
(
f
a
log
b
ε
−
=
)
n
(
)
n
(
f
a
log
b
Θ
=
)
n
log
n
(
)
n
(
T
a
log
b
Θ
=
)
n
(
)
n
(
f
a
log
b
ε
+
Ω
=
78
Algorytmy i struktury danych
Interpretacja
W każdym z trzech przypadków porównujemy funkcję
f(n)
z funkcją
Rozwiązanie rekurencji zależy od większej z tych dwóch funkcji
Jeśli funkcja jest większa (Przypadek 1), to rozwiązaniem rekurencji
jest
Jeśli funkcja
f(n)
jest większa (Przypadek 3), to rozwiązaniem jest
T(n) =
Θ
(f(n))
Jeśli funkcje są tego samego rzędu (Przypadek 2), to rozwiązaniem jest
,
czyli
T(n) =
Θ
( f(n) log n)
Metoda rekurencji uniwersalnej
a
log
b
n
)
n
log
n
(
)
n
(
T
a
log
b
Θ
=
a
log
b
n
)
n
(
)
n
(
T
a
log
b
Θ
=
79
Algorytmy i struktury danych
Przykład 1
Określić oszacowanie asymptotyczne dla rekurencji:
T(n) = 9 T(n/3) + n
Mamy:
a=9
,
b=3
,
f(n)=n
, a zatem
Ponieważ
, gdzie
ε
=1
, możemy zastosować przypadek 1
twierdzenia o rekurencji uniwersalnej i wnioskować że rozwiązaniem jest
T(n) =
Θ
Θ
Θ
Θ
( n
2
)
Metoda rekurencji uniwersalnej
2
9
log
a
log
n
n
n
3
b
=
=
)
n
(
O
)
n
(
f
9
log
3
ε
−
=
80
Algorytmy i struktury danych
Przykład 2
Określić oszacowanie asymptotyczne dla rekurencji:
T(n) = T(2n/3) + 1
Mamy:
a=1
,
b=3/2
,
f(n)=1
, a zatem
Stosujemy przypadek 2, gdyż
a zatem rozwiązaniem rekurencji jest
Metoda rekurencji uniwersalnej
1
n
n
n
0
1
log
a
log
2
3
b
=
=
=
)
1
(
)
n
(
)
n
(
)
n
(
)
n
(
f
0
1
log
a
log
2
3
b
Θ
=
Θ
=
Θ
=
Θ
=
)
n
(log
)
n
log
n
(
)
n
log
n
(
)
n
(
T
1
log
a
log
2
3
b
Θ
=
Θ
=
Θ
=
81
Algorytmy i struktury danych
Przykład 3
Określić oszacowanie asymptotyczne dla rekurencji:
T(n) = 3T(n/4) + n log n
Mamy:
a=3
,
b=4
,
f(n)=n log n
, a zatem
Ponieważ
, gdzie
ε
~ 0.2
, więc stosuje się tutaj przypadek
3, jeśli możemy pokazać, że dla
f(n)
zachodzi warunek regularności
Dla dostatecznie dużych
n
możemy napisać:
a f(n/b) = 3 (n/4) log (n/4)
≤
(3/4) n log n = c f(n), przy czym c=¾ < 1
Warunek regularności jest zatem jest spełniony i możemy napisać, że
rozwiązaniem rekurencji jest
T(n) =
Θ
Θ
Θ
Θ
[f(n)] =
Θ
Θ
Θ
Θ
(n log n)
Metoda rekurencji uniwersalnej
793
,
0
3
log
a
log
n
n
n
4
b
=
=
)
n
(
)
n
(
f
3
log
4
ε
+
Ω
=
82
Algorytmy i struktury danych
Przykład 4
Określić oszacowanie asymptotyczne dla rekurencji:
T(n) = 2T(n/2) + n log n
Mamy:
a=2
,
b=2
,
f(n)=n log n
, a zatem
Wydaje się, że powinien to być przypadek 3, gdyż
f(n)=n log n
jest
asymptotycznie większe niż (ale nie wielomianowo!)
Stosunek jest asymptotycznie mniejszy niż
n
ε
dla
każdej dodatniej stałej
ε
.
W konsekwencji rekurencja ta “wpada” w lukę między przypadkiem 2 i 3.
Nie można zatem zastosować twierdzenia o rekurencji uniwersalnej
Metoda rekurencji uniwersalnej
n
n
a
log
b
=
n
n
a
log
b
=
n
/
n
log
n
n
/
)
n
(
f
a
log
b
=
83
Algorytmy i struktury danych
Zadanie
Wykorzystując metodę rekurencji uniwersalnej określić oszacowanie
asymptotyczne dla rekurencji:
a) T(n) = 2 T(n/2) + n
b) T(n) = T(2n/3) + 1
84
Algorytmy i struktury danych
Wyszukiwarka
Podobne podstrony:
AiSD W1 1
Farmakologia pokazy, Podstawy Farmakologii Ogólnej (W1)
W1 wprow
Przygotowanie PRODUKCJI 2009 w1
w1 czym jest psychologia
PD W1 Wprowadzenie do PD(2010 10 02) 1 1
wde w1
Finanse W1
W1 ZLO
AM1 2005 W1
w1
więcej podobnych podstron