Rekursionsgleichung Induktion < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 19:07 Do 24.11.2011 | | Autor: | MISTERX |
| Aufgabe | Löse die Rekursionsgleichung durch Induktion:
[mm] T(n)=\begin{cases} Theta(1) & \mbox{für } n \mbox{ =1} \\ 8T(n/2)+n, & \mbox{für } n \mbox{ >1} \end{cases} [/mm] |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
ich habe die Aufgabe folgendermaßen versucht zu lösen :
Behauptung: T(n) <= [mm] cn^2 [/mm]
IA: für Abbruchbedingung n= 1
T(1) = 1
1 <= [mm] c*n^2
[/mm]
1 <= c gilt für c=1
IV: T(n ) <= [mm] 1*n^2
[/mm]
8T(n/2)+n <= [mm] 1*n^2 [/mm] (nach IV)
IS: n --> 2n
T(2n) <= [mm] (2n)^2
[/mm]
8T(2n/2) + 2n <= [mm] (2n)^2
[/mm]
8T( n) + 2n <= [mm] 4n^2
[/mm]
8 T(n ) + 2n <= [mm] 8*n^2 [/mm] + 2n (nach IV)
[mm] 8n^2 [/mm] + 2n <= [mm] (2n)^2
[/mm]
[mm] 8n^2 [/mm] + 2n <= [mm] 4n^2 [/mm]
--> aber das geht nicht auf, die Ungleichung stimmt ja nicht.
Was habe ich hier falsch gemacht? Wie macht man das richtig?
Vielen Dank für Eure Hilfe!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 So 27.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
