xole_X
Grünschnabel
Dabei seit: 23.10.2007
Beiträge: 9
![](images/spacer.gif) |
|
rekurrenzgleichung beweisen |
![Zum Anfang der Seite springen Zum Anfang der Seite springen](images/goup.gif) |
Ich soll zeigen, dass
T(n) = T(0.5n + 10) + n in O(n*lg(n)) liegt...
wie mach ich das am besten?
ich habs folgender maßen probiert:
T(n)<=c* (0.5n+10)*lg(0.5n+10)+n
jetzt nehm ich als abschätzung 0.5n+10<=n gilt für alle n>= 20
<= c*(0.5n+10)*lg(n)+n<=c*n*lg(n) ----> aber ab welchem n gilt das hier bei c=1 zB...ab ca 300 hab am graph abgelesen, aber wie gesagt, abgelesen und nicht errechnet...naja das waren jetzt so meine erfolglosen versuche...hoffe mir kann jemand helfen
|
|
28.04.2008 22:43 |
|
|
Tobias
Routinier
![](images/star2.gif) ![](images/star2.gif)
Dabei seit: 18.09.2006
Beiträge: 324
![](images/spacer.gif) |
|
|
29.04.2008 14:16 |
|
|
![](images/spacer.gif) |
xole_X
Grünschnabel
Dabei seit: 23.10.2007
Beiträge: 9
![](images/spacer.gif) |
|
ja kenn das mastertheorem, aber was mach ich denn mit der 10 in T(n) = T(0.5n + 10)
Das Mastertheorem ist doch nur für Gleichungen der Form:
T(n) = a*T(n/b)+f(n)
a ist bei meiner gleichung : a=1 aber was ist b?
|
|
29.04.2008 15:28 |
|
|
![](images/spacer.gif) |
xole_X
Grünschnabel
Dabei seit: 23.10.2007
Beiträge: 9
![](images/spacer.gif) |
|
|
29.04.2008 16:32 |
|
|
Tobias
Routinier
![](images/star2.gif) ![](images/star2.gif)
Dabei seit: 18.09.2006
Beiträge: 324
![](images/spacer.gif) |
|
b ist 2 wegen
Zitat: |
Für fällt die Konstante 10 nicht mehr ins Gewicht. Man kann also sogleich sagen, dass für ein geeignetes f. |
|
|
29.04.2008 15:48 |
|
|
Tobias
Routinier
![](images/star2.gif) ![](images/star2.gif)
Dabei seit: 18.09.2006
Beiträge: 324
![](images/spacer.gif) |
|
|
29.04.2008 18:02 |
|
|
![](images/spacer.gif) |
xole_X
Grünschnabel
Dabei seit: 23.10.2007
Beiträge: 9
![](images/spacer.gif) |
|
[quote]Original von Tobias
Deshalb schrieb ich ja schon, dass das Mastertheorem beweist, dass ![[latex]T(n) \in \Theta(n)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?T(n) \in \Theta(n))
[quote]
kann ich sagen, die aussage stimmt, da
|
|
29.04.2008 18:10 |
|
|
Tobias
Routinier
![](images/star2.gif) ![](images/star2.gif)
Dabei seit: 18.09.2006
Beiträge: 324
![](images/spacer.gif) |
|
Es ist wieder einmal Zeit, sich selbst zu zitieren:
Zitat: |
Kennst du das Master-Theorem? Damit beweist man, dass sogar und damit natürlich auch ![[latex]T(n) \in \mathcal{O}(n\log n)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?T(n) \in \mathcal{O}(n\log n)) |
Zitat: |
kann ich sagen, die aussage stimmt, da ![[latex]T(n) \in \Theta(n) <= O(n*lg(n))[/latex]](http://www.matheboard.de/latex2png/latex2png.php?T(n) \in \Theta(n) <= O(n*lg(n))) |
Ja, das kann man sagen. Die Schreibweise ist ein wenig unorthodox aber ich denke man weiß, was du sagen willst. Strenger formuliert müsste es so lauten:
|
|
29.04.2008 18:49 |
|
|
|
![Antwort erstellen Antwort erstellen](images/reply.gif) |
|