Laufzeit beweisen < Induktion < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:09 Do 21.04.2011 | | Autor: | Erstie |
| Aufgabe | T(1) = 1
T(n) = 4T(n/2) + 6n:
Zeigen Sie, dass für beliebige Zweierpotenzen n gilt, dass T(n) = [mm] O(n^2) [/mm] ist. (Tipp: Induktion!) |
Hallo,
Ich habe diese Aufgabe folgendermaßen nach der Substituionsmethode gelöst:
Zu zeigen: [mm] T(n)=O(n^2)
[/mm]
Induktionsanfang für n=1:
[mm] T(1)=1^2=1 [/mm] ->korrekt
Induktionsvoraussetzung: [mm] T(n)=n^2
[/mm]
Induktionsschritt: n/2 -> n
T(n)= 4*T(n/2) + 6n
= [mm] 4*(n/2)^2 [/mm] + 6n
= [mm] 4*(n^2/4) [/mm] + 6n
= [mm] n^2 [/mm] + 6n
Da [mm] (n^2+6n)/n^2 [/mm] = 1+(6/n) gegen 1 konvergiert und [mm] 0<=1<\infty, [/mm] gilt [mm] T(n)=O(n^2)
[/mm]
Ist der Indutkionsschritt so richtig?
Diese Aufgabe wurde leider nicht besprochen, aber es wurde gesagt, dass wir auf T(n)<= [mm] 7n^2-6n [/mm] die vollständige Induktion anwenden sollen.
Mir ist nicht klar, wie man von T(n)=4T(n/2)+6n auf [mm] T(n)<=7n^2-6n [/mm] kommt.
Ich hoffe ihr könnt mir weiterhelfen.
Gruß Erstie
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:42 Do 21.04.2011 | | Autor: | fred97 |
> T(1) = 1
> T(n) = 4T(n/2) + 6n:
> Zeigen Sie, dass für beliebige Zweierpotenzen n gilt,
> dass T(n) = [mm]O(n^2)[/mm] ist. (Tipp: Induktion!)
> Hallo,
>
> Ich habe diese Aufgabe folgendermaßen nach der
> Substituionsmethode
Was iat das denn ?
> gelöst:
>
> Zu zeigen: [mm]T(n)=O(n^2)[/mm]
Zum Beweis dieser Aussage ist Induktion nun wahrlich nicht geeignet !!
Du sollst zeigen: die Folge [mm] (\bruch{T(2^k)}{2^{2k}}) [/mm] ist beschränkt.
>
> Induktionsanfang für n=1:
> [mm]T(1)=1^2=1[/mm] ->korrekt
>
> Induktionsvoraussetzung: [mm]T(n)=n^2[/mm]
>
> Induktionsschritt: n/2 -> n
> T(n)= 4*T(n/2) + 6n
> = [mm]4*(n/2)^2[/mm] + 6n
> = [mm]4*(n^2/4)[/mm] + 6n
> = [mm]n^2[/mm] + 6n
>
> Da [mm](n^2+6n)/n^2[/mm] = 1+(6/n) gegen 1 konvergiert und
> [mm]0<=1<\infty,[/mm] gilt [mm]T(n)=O(n^2)[/mm]
>
> Ist der Indutkionsschritt so richtig?
>
> Diese Aufgabe wurde leider nicht besprochen, aber es wurde
> gesagt, dass wir auf T(n)<= [mm]7n^2-6n[/mm] die vollständige
> Induktion anwenden sollen.
Also: zeige induktiv: [mm] T(2^k) \le 7*2^{2k}-6*2^k$ [/mm] für k [mm] \in \IN
[/mm]
Wenn Du das geschafft hast , ist die Beschränktheit der Folge [mm] (\bruch{T(2^k)}{2^{2k}}) [/mm] sehr einfach zu zeigen.
FRED
>
> Mir ist nicht klar, wie man von T(n)=4T(n/2)+6n auf
> [mm]T(n)<=7n^2-6n[/mm] kommt.
> Ich hoffe ihr könnt mir weiterhelfen.
>
> Gruß Erstie
>
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:43 Do 21.04.2011 | | Autor: | Erstie |
Vielen Dank für die schnelle Antwort.
Dein Hinweis hilft mir da schon etwas weiter.
Mir ist aber immer noch nicht klar, wie man auf T(n)<= $ [mm] 7n^2-6n [/mm] $ kommt. Diese Formel wurde in der Aufgabe nicht vorgegeben.
Hoffe, ihr könnt mir da weiterhelfen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:26 Do 21.04.2011 | | Autor: | leduart |
Hallo
in freds post stand doch wörtlich
"Also: zeige induktiv: $ [mm] T(2^k) \le 7\cdot{}2^{2k}-6\cdot{}2^k$ [/mm] für $k [mm] \in \IN [/mm] $"
da stand nix davon dass die formel "gegeben" ist.
Gruss leduart
|
|
|
|
