Rekursive Zeitgleichungen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe 1 | Geg. ist folgende Gleichung:
T(n) = 5T(n-3)
Gesucht ist eine asymptotische Schranke. |
| Aufgabe 2 | T(n) = [mm] 4T(\frac{n}{5}) [/mm] + O(1)
Gesucht ist ebenfalls eine asymptotische Schranke. |
Bis jetzt bin ich auf dem Ergebnis T(n) = [mm] 5^k [/mm] * T(n-3*k)
und k = [mm] \bruch{1}{n-3} [/mm] mittels der Methode des iterativen Einsetzens gekommen.
Wie komm ich jetzt auf die obere Schranke ( O(...) )?
Beim 2. Beispiel würde micht interessieren, ob ich hier die Mastermethode anwenden kann? und falls JA, wie?
Oder kann man hier vielleicht sogar die Substitutionsmethode verwenden?
lg
Thomas4
|
|
| |
|
Hallo Thomas,
vielleicht verstehe ich ja nur die Notation nicht, aber so sind die Aufgabenstellungen wenig sinnvoll.
(1)
> Geg. ist folgende Gleichung:
>
> T(n) = 5T(n-3)
>
> Gesucht ist eine asymptotische Schranke.
(2)
> T(n) = [mm]4T(\frac{n}{5})[/mm] + O(1)
>
> Gesucht ist ebenfalls eine asymptotische Schranke.
Zu (1)
> Bis jetzt bin ich auf dem Ergebnis T(n) = [mm]5^k[/mm] * T(n-3*k)
> und k = [mm]\bruch{1}{n-3}[/mm] mittels der Methode des iterativen
> Einsetzens gekommen.
> Wie komm ich jetzt auf die obere Schranke ( O(...) )?
Nehmen wir mal ein Beispiel. Sei T(1)=0, T(2)=-0,3714 und T(3)=200.001.229
Dann definiert die rekursive Formel faktisch drei verschiedene Folgen, die vollkommen unabhängig voneinander sind. Sei [mm] m\in\IN_0.
[/mm]
Die eine umfasst T(1), T(4), T(7), ..., T(3m+1) und ist konstant Null.
Die zweite umfasst alle T(3m+2) und strebt gegen [mm] -\infty.
[/mm]
Die dritte umfasst alle T(3m) und strebt gegen [mm] +\infty.
[/mm]
Und nun?
Zu (2)
> Beim 2. Beispiel würde micht interessieren, ob ich hier
> die Mastermethode anwenden kann? und falls JA, wie?
>
> Oder kann man hier vielleicht sogar die
> Substitutionsmethode verwenden?
Sagt mir nichts, was wahrscheinlich an mir liegt.
Was ist O(1)? Und wieso darf man n einfach fünfteln?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Mo 01.10.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
