Rekursive Zeitgleichung < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 14:59 Mi 22.04.2009 | | Autor: | maecky |
| Aufgabe | Loesen Sie die folgende rekursive Zeitgleichung auf. Sie koennen dabei die in der Vorlesung besprochenen Methoden verwenden, muessen aber alle Ihre Zwichenschritte angeben.
T(n) = T(n-2)-T(n-4) |
Die Methoden die wir in der Vorlesung besprochen haben sind:
Master Methode
Iterative Methode
Substitutions Methode
Die Master Methode kann hier meiner Meinung nach nicht angewendet werden, darum habe ich es einmal mit der iterativen Methode versucht:
1: T(n) = - T( n-6 )
2: T(n) = - T( n-8 ) + T( n-10 )
3: T(n) = +T( n-12 )
4: T(n) = +T( n-14 ) - T( n-16 )
5: T(n) = - T( n-18 )
usw.
Ich kann irgendwie keine Regelmaessigkeit finden und somit auch keine Schranke herleiten.
Wenn jemand einen Tip hat und mir helfen koennte wuerde ich mich sehr freuen.
mfg maecky
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:06 Mi 22.04.2009 | | Autor: | Gilga |
was wäre denn wenn man O(1) als Schranke verwendet?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 Sa 23.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
