rekursive funktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | [mm] T(n)=\begin{cases} 2, & \mbox{für } n = 2 \\ 2T(\bruch{^n}{2})+n, & \mbox{für } n = 2^{k} , k > 1 \end{cases}
[/mm]
Zeige per Induktion, dass wenn n eine Potenz von 2, also n = [mm] 2^{k} \Rightarrow [/mm] T(n) = n [mm] log_{2} [/mm] n |
Annahme:
[mm] T(2^{k}) [/mm] = n [mm] log_{2}n
[/mm]
Induktionsbeginn:
Sei k = 1
[mm] \Rightarrow [/mm] n = [mm] 2^{1} [/mm] = 2 [mm] \Rightarrow [/mm] T(2) = 2 = 2 [mm] log_{2}2 [/mm] = n [mm] log_{2} [/mm] n
Induktionsschritt:
k [mm] \mapsto [/mm] k+1
[mm] T(2^{k+1}) [/mm] = [mm] 2T(2^{k})+2^{k+1} [/mm] nach Definition von T(n)
Nach Annahme gilt [mm] T(2^{k}) [/mm] = [mm] 2^{k} log_{2}2^{k}
[/mm]
[mm] \Rightarrow 2T(2^{k}) [/mm] + [mm] 2^{k+1} [/mm] = [mm] 2*2^{k} log_{2}2^{k} [/mm] + [mm] 2^{k+1} [/mm] = [mm] 2^{k+1}log_{2}2^{k}+2^{k+1}*log_{2}2 [/mm] = [mm] 2^{k+1}(log_{2}2^{k} [/mm] + [mm] log_{2}2) [/mm] = [mm] 2^{k+1}*log_{2}(2^{k}*2) [/mm] = [mm] 2^{k+1}*log_{2}2^{k+1} [/mm] = [mm] n*log_{2}n \Box
[/mm]
w.z.b.w. (was zu befürchten war!)
Und ich dachte schon ich wäre doof!
Mit der richtigen Funktion ist das natürlich viel einfacher zu beweisen!
Danke, Gruß, und sorry für die Fehler :D
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:35 So 18.11.2007 | | Autor: | Loddar |
Hallo JROppenheimer!
Aus $n \ = \ [mm] 2^k$ [/mm] folgt doch $k \ = \ [mm] \log_{2}(n) [/mm] $ . Setze dies mal in Deinen Induktionsschritt ein.
Gruß
Loddar
|
|
|
| |
|
Im Induktionsschritt arbeite ich aber doch mit n = k+1. Bzw. ich wüsste jetzt nicht genau an welcher Stelle, ich das verwenden sollte...
Könntest Du das ETWAS genauer beschreiben?
Musst es nicht lösen, aber wäre nett, wenn Du mir noch ein bisschen auf die Sprünge helfen könntest.
Danke!
|
|
|
| |
|
Ich hab gerade mal bissie rumprobiert, aber irgendwie geht das bei mir auch nicht auf mit dem n log n
gegeben ist die reurssive Funktion:
$ [mm] T(n)=\begin{cases} 2, & \mbox{für } n = 2 \\ 2T(\bruch{^n}{2}), & \mbox{für } n = 2^{k} , k > 1 \end{cases} [/mm] $
okay....schrittweise:
T(2) = 2
T(4) = 2T(2) = 4
T(8) = 2T(4) = 8
.
.
.
oder steh ich gerade so krass aufm schlauch?!
|
|
|
| |
|
*räusper .... mir ist ein schwerwiegender Fehler unterlaufen .... die rekursive Funktion lautet anders....
$ [mm] T(n)=\begin{cases} 2, & \mbox{für } n = 2 \\ 2T(\bruch{^n}{2})+n, & \mbox{für } n = 2^{k} , k > 1 \end{cases} [/mm] $
Ich hoffe ihr könnt mir verzeihen ... ich fang noch mal von vorn an!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:31 Mo 19.11.2007 | | Autor: | Karl_Pech |
Hallo JROppenheimer,
Folgende Aufgabe ist deiner ähnlich.
Viele Grüße
Karl
|
|
|
|
