Laufzeitberechnung < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | a) T(n) = T(n-2) - T(n-4)
b) T(n) = T(n-1) |
Hallo,
hab ein kleines Problem beim den obigen Laufzeitberechnungen.
bei a) setze ich iterativ weiß aber nicht ob die Lösung so stimmt, das minus wirft mich hier irgendwie aus der Bahn:
T(n) = T(n-2) - T(n-4)
T(n-2) = T(n-4) - T(n-6)
T(n-4) = T(n-6) - T(n-8)
T(n) = T(n-4) - T(n-6) - T(n-4) .... T(n-4)-T(n-4) = T(n-4)
T(n) = T(n-6) - T(n-6) - T(n-8) .... T(n-6)-T(n-6) = T(n-6)
T(n) = T(n-k) - T(n - (k+2))
mit T(1) = O(1) ergibt sich n = k;
-->n Aufrufe --> T(n) = O(n)
b) kann ich hier auch T(n) = T(n-1) +O(1) schreiben
sodass ich schlussendlich auf T(n-k)+k*O(1) komme und mit k=n O(n) als Lösung erhalte?
lg Tom
|
|
| |
|
Hallo Tom,
> a) T(n) = T(n-2) - T(n-4)
> b) T(n) = T(n-1)
> Hallo,
>
> hab ein kleines Problem beim den obigen
> Laufzeitberechnungen.
>
> bei a) setze ich iterativ weiß aber nicht ob die Lösung
> so stimmt, das minus wirft mich hier irgendwie aus der
> Bahn:
> T(n) = T(n-2) - T(n-4)
> T(n-2) = T(n-4) - T(n-6)
> T(n-4) = T(n-6) - T(n-8)
> T(n) = T(n-4) - T(n-6) - T(n-4) .... T(n-4)-T(n-4) =
> T(n-4)
> T(n) = T(n-6) - T(n-6) - T(n-8) .... T(n-6)-T(n-6) =
> T(n-6)
>
> T(n) = T(n-k) - T(n - (k+2))
>
> mit T(1) = O(1) ergibt sich n = k;
>
> -->n Aufrufe --> T(n) = O(n)
Wegen
T(n) = T(n-2) - T(n-4)
und
T(n-2) = T((n-2)-2) - T((n-2)-4) = T(n-4) - T(n-6)
komme ich auf das zugegebenermaßen komische Ergebnis:
T(n ) = -T(n-6).
und weiter
T(n) = T(n-12).
Zu b):
> b) kann ich hier auch T(n) = T(n-1) +O(1) schreiben
Nein. Wenn, dann T(n) = T(n-1) + O(0).
> sodass ich schlussendlich auf T(n-k)+k*O(1) komme und mit
> k=n O(n) als Lösung erhalte?
Nein. Die Laufzeit ist O(1).
Die Rekursionsformel sagt doch nichts anderes aus, als dass die Laufzeit bei n "Daten" genau dieselbe ist wie bei n-1 "Daten". Also erhältst du:
T(n) = T(n-1) = ... = T(1).
Du musst also nur noch wissen, wie sich die Laufzeit bei T(1) verhält, und das ist dann auch die von T(n).
Grüße,
Stefan
|
|
|
|
