rekursive zeitgleichung < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:48 Mi 05.11.2008 | | Autor: | alpman |
| Aufgabe | Sei a,b e N; a,b > 2. Zeigen sie eine obere Schranke für folgende rekursive Zeitgleichung (durch iteriertes Einsetzen):
[mm] T(n)=a*T(\bruch{n}{a})+n^{b}
[/mm]
T(1)=O(1).
|
Mir fehlt der Ansatz, wie ich dieses Probelm angehen soll. Hab noch nicht rausgefunden wie es mit 2 versch. variablen funktionieren soll.
mfg Arno
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:54 Mi 05.11.2008 | | Autor: | Bastiane |
Hallo alpman!
> Sei a,b e N; a,b > 2. Zeigen sie eine obere Schranke für
> folgende rekursive Zeitgleichung (durch iteriertes
> Einsetzen):
> [mm]T(n)=a*T(\bruch{n}{a})+n^{b}[/mm]
> T(1)=O(1).
>
> Mir fehlt der Ansatz, wie ich dieses Probelm angehen soll.
> Hab noch nicht rausgefunden wie es mit 2 versch. variablen
> funktionieren soll.
Wo hast du denn zwei Variablen? Das Ganze hängt doch nur von n ab. Versuche es mal genauso wie wenn du statt a und b Zahlen da stehen hast. Entweder einsetzen und umformen, oder vllt auch mit dem Mastertheorem, falls ihr das schon hattet und benutzen dürft.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:28 Do 06.11.2008 | | Autor: | fin129 |
Hallo,
mir würde spontan einfallen, erstmal o.B.d.A. [mm]n = a^{k}[/mm] anzunehmen.
Dadurch würde dann [mm]T(n)[/mm] zu [mm]a*T(a^{k-1}) + n^b[/mm]
Ein, zwei mal einsetzen, dann für die i-te Stufe eine Formel finden, danach [mm]k:=i[/mm] setzen um auf eine Formel mit [mm]T(1)[/mm] zu kommen. aus k wieder n durch logarithmieren machen, Schranke finden und nachweisen und ggf. argumentieren, dass Logarithmen zu unterschiedlichen Basen sich nur um konstante Faktoren unterscheiden.
lg
fin
|
|
|
|
