chiller
unregistriert
 |
|
| Explizite Formel zur Rekursionsformel in O-Notation |
     |
Meine Frage:
Hallo,
ich muss eine explizite Formel zu folgenden Rekursionsformel herleiten:
![[latex]T(n) <= c [/latex]](http://www.matheboard.de/latex2png/latex2png.php?T(n) <= c )
bei c ist n=1
![[latex]T(n) <= 4T(n/2)+cn [/latex]](http://www.matheboard.de/latex2png/latex2png.php?T(n) <= 4T(n/2)+cn )
bei der Formel n>1
Meine Ideen:
Ich bin durch das einsetzen auf diese Formel gekommen:
![[latex]i^2T(\frac{n}{i})+\frac{3}{4} icn+cn [/latex]](http://www.matheboard.de/latex2png/latex2png.php?i^2T(\frac{n}{i})+\frac{3}{4} icn+cn )
Ist diese richtig? Wenn ja, wie komme ich denn von dieser Formel auf eine O-Notation?
Durch Raten bin ich auf das hier gekommen:
![[latex]nT(1)+O(n)+O(n)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?nT(1)+O(n)+O(n))
Bitte fragt mich nicht wie ich auf die O-Notation gekommen bin. Ist halt nur geraten.
Ich danke euch schon mal für eure Hilfe.
|
|
26.05.2011 20:13 |
|
|
