asymtotische obere Schranke < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:00 Mi 03.11.2004 | | Autor: | jOnEs |
Hallo, ich habe leider keine Ahnung von dieser Aufgabe & würde mich sehr freuen, wenn ich hier Hilfe finde ...
die Aufgabe lautet: "Bestimmen Sie asymptotische obere Schranken für T(n) in der folgenden Rekurrenz.
T(n) = [mm] \wurzel{n} T(\wurzel{n}) [/mm] + n
Danke schon einmal im voraus für die Hilfe ...
|
|
| |
|
Hallo jOnEs,
mir kommt das etwas komisch vor, weil du ja mit [mm]T(\sqrt{n})[/mm] auf gewissermaßen undefinierte Ausdrücke zurückgreifst, aber lassen wir diesen Kritikpunkt mal außer acht.
Nimm an du kennst für [mm]n>1[/mm] die Zahl [mm]T(n)[/mm].
Dann kannst du daraus [mm]T(n^2)=n\cdot T(n)+n^2[/mm] berechnen.
Dann kannst du auch [mm]T((n^2)^2)=T(n^4)[/mm], [mm]T(n^8)[/mm] usw. berechnen und auf [mm]T(n)[/mm] zurückführen.
Aus dem Aussehen dieser Terme ergibt sich vielleicht was.
Hugo
|
|
|
|
