wyklad 13, AGH, WFiIS, Informatyka stosowana, Semestr I, matma dyskretna-misztal, wyklad
[ Pobierz całość w formacie PDF ]
Twierdzenie o rekurencji uniwersalnej
na podstawie ”Slides
c
2005, 2010 by M. J. Golin, G. Trippen”
Wykład13
29 maja 2012
(Wykład13)
Twierdzenieorekurencjiuniwersalnej
29maja2012 1/32
Outline
1
Twierdzenie o rekurencji uniwersalnej
2
Podłoga i sufit
3
Zaawansowane przykłady indukcji matematycznej
(Wykład13)
Twierdzenieorekurencjiuniwersalnej
29maja2012 2/32
Twierdzenie o rekurencji uniwersalnej
Lemat (4.7)
Załó»my,»erównanierekurencyjnemaposta¢
T
(
n
)=
aT
(
n
2
)+
n
,gdzie
a2Z
+
,
T(1)2N
.Wtedyrozwi¡zanierównaniajestpostaci:
1
je»eli
a<2
,to
T(n)=Q(n)
.
2
je»eli
a
=
2
,to
T
(
n
)=
(
nlog
2
(
n
))
.
3
je»eli
a>2
,to
T(n)=Q(n
log
2
(
a
)
)
.
Q
Nie ma powodu by
T
(
n
2
)
- rozmiar podproblemu był zawsze połow¡ rozmiaru problemu
oryginalnego.
f
(
n
)=
n
- zło»ono±¢ cz¦±ci nierekurencyjnej była zawsze równa
n
.
(Wykład13)
Twierdzenieorekurencjiuniwersalnej
29maja2012 3/32
Twierdzenie o rekurencji uniwersalnej
Twierdzenie (4.9)
Załó»my,»erównanierekurencyjnemaposta¢
aT(
n
b
)+n
c
,
dla
n>1
T
(
n
)=
d,
dla
n
=
1
,
gdzie
a2Z
+
,
b2R
,
b>1
,
c2R
+
,
d2N
,
n
jestpot¦g¡dwójki.Wtedy
rozwi¡zanierównaniajestpostaci:
1
je»eli
log
b
a
<
c
,to
T
(
n
)=
Q
(
n
c
)
.
2
je»eli
log
b
a=c
,to
T(n)=Q(n
c
logn)
.
3
je»eli
log
b
a
>
c
,to
T
(
n
)=
Q
(
n
log
b
a
)
.
(Wykład13)
Twierdzenieorekurencjiuniwersalnej
29maja2012 4/32
Twierdzenie o rekurencji uniwersalnej
Dowód.
Dla uproszczenia załó»my, »e
d
=
1
.
Rozwa»my drzewo rekursji powy»szej rekurencji.
W drzewie rekursji b¦dzie
1
+
log
b
n
poziomów.
Na ka»dym poziomie, liczba podproblemów zostanie pomno»ona przez
a
, zatem liczba podproblemów na poziomie
i
wyniesie
a
i
.
Ka»dy podproblem na poziomie
i
ma rozmiar
n/b
i
, podproblem o
takim rozmiarze wymaga
(
n/b
i
)
c
dodatkowej pracy, a skoro jest
takich pobproblemów
a
i
, to miar¡ wykonanej pracy na poziomie
i
, jest
a
i
(n/b
i
)
c
=n
c
(
a
i
b
ic
)=n
c
(
a
b
c
)
i
.
Ilo±¢ pracy na danym poziomie zale»y od zachowania
(
a
b
c
)
i
.
Ilo±¢ pracy maleje, pozostaje stała, b¡d¹ ro±nie, kiedy
(
a
b
c
)
i
, jest
mniejsze ni»
1
, równe
1
, lub wi¦ksze ni»
1
.
(Wykład13)
Twierdzenieorekurencjiuniwersalnej
29maja2012 5/32
[ Pobierz całość w formacie PDF ]