Algorithmen und Berechnungshomplexität
Präsenzblatt 2
21
Aufgabe ,
begeben sei die folgende Rekursionsvorschrift TIN IN mit :
falls
[cn-1)
, n =1
T(m) =
+ 3ni
falls na
Ziel ist es nun , eine
geschlossene Form TCns für diese
Rekursionsvorschrift zu finden und per
vollständige Induktion zu beweisen .
Betrachtet man die ersten Werte :
TG) =
3
T(2) TH) + 3 2 3 + 6
= .
= =
9
T(3) T(2) + 3 3 g + 9 18
= . = =
T(4) +(3) + 3 4 18 + 12 38
= .
=
=
, Differenzen TCn) -TCn-1) In
Die nahe =
legen ,
dass Tens die Summe einer arithmetischen Folget
T(n) 3 + 3 =
.
2+ 3 3 +... + 3n
1
Dies entspricht der Summe :
T(n) = 3h =
3 .
hin
+)
_
3n(n)
2
k 1
=
Die Behauptung kann per vollständiger Induktion bewiesen werden :
Induktionsanfang
Fürn =
+ 1)
311(1 3
12 2 3
,
T(1) = = = =
Induktionsannahme
Es gelte die
geschlossene Rekussionsvorschrift
für ein beliebiges n21 :
3n(n + 1)
T(n) =
2
Präsenzblatt 2
21
Aufgabe ,
begeben sei die folgende Rekursionsvorschrift TIN IN mit :
falls
[cn-1)
, n =1
T(m) =
+ 3ni
falls na
Ziel ist es nun , eine
geschlossene Form TCns für diese
Rekursionsvorschrift zu finden und per
vollständige Induktion zu beweisen .
Betrachtet man die ersten Werte :
TG) =
3
T(2) TH) + 3 2 3 + 6
= .
= =
9
T(3) T(2) + 3 3 g + 9 18
= . = =
T(4) +(3) + 3 4 18 + 12 38
= .
=
=
, Differenzen TCn) -TCn-1) In
Die nahe =
legen ,
dass Tens die Summe einer arithmetischen Folget
T(n) 3 + 3 =
.
2+ 3 3 +... + 3n
1
Dies entspricht der Summe :
T(n) = 3h =
3 .
hin
+)
_
3n(n)
2
k 1
=
Die Behauptung kann per vollständiger Induktion bewiesen werden :
Induktionsanfang
Fürn =
+ 1)
311(1 3
12 2 3
,
T(1) = = = =
Induktionsannahme
Es gelte die
geschlossene Rekussionsvorschrift
für ein beliebiges n21 :
3n(n + 1)
T(n) =
2
