Rekursiver Algorithmus - Laufzeit berechnen |
14.10.2014, 11:04 | Gordy | Auf diesen Beitrag antworten » |
Rekursiver Algorithmus - Laufzeit berechnen Ich hoffe jemand kann mir bei meinem Problem helfen. Ich habe einen rekursiven Algorithmus, von welchem ich die Laufzeit bestimmen soll. Kurz der Pseudocode des Algorithmus, welche auf einer n*m Matrix M operiert. recursion(t, s) M[t,s] = recursion( t-1, s ) + 2*recursion( t, s-1 ) + 3*recursion( t-1, s-1 ) Meine Idee wäre zu sagen dass das prinzipiell T(n) = T(n-1) +2T(n-1) +3T(n-2) = 3T(n-1)+3T(n-2) ist, kann man das so sagen? Das bedeutet, dass jeder Funktionsaufruf, 2 neue Aufrufe bewirkt und die Laufzeit deswegen O() ist? Vielen Dank schon mal! |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |