| Die letzten 4 Beiträge |
| Shizmo |
Ups, da stimmt 
|
| eulerscheZahl |
Für das Mastertheorem braucht man ja als rekursiven Aufruf: ![[latex]a\cdot T(\frac n b)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?a\cdot T(\frac n b))
Das scheitert schon daran, dass hier eine Wurzel steht.
Du kannst die Wurzel wegsubstituieren.
Siehe math.stackexchange.com |
| Shizmo |
Ich glaube du versuchst es mit dem Master-Theorem abzuschätzen, richtig?
Dein b wäre 1, da das aber nicht sein darf (b muss größer gleich 2 sein), gibt es nur 2 Möglichkeiten, entweder man kann das Master-Theroem nicht anwenden, oder man macht einen Trick, aber ob man das darf weiß ich nicht 
![[latex]T(n) = 2\cdot T(\frac{2\cdot\sqrt{n}}{2})+\log_2(n)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?T(n) = 2\cdot T(\frac{2\cdot\sqrt{n}}{2})+\log_2(n))
![[latex]\Rightarrow a=2, b=2, f(n)=\log_2(n)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\Rightarrow a=2, b=2, f(n)=\log_2(n))
Somit ist ![[latex]f\in\mathcal{O}(n^{\log_b(a)-\epsilon})[/latex]](http://www.matheboard.de/latex2png/latex2png.php?f\in\mathcal{O}(n^{\log_b(a)-\epsilon}))
![[latex]\Rightarrow \Theta(n)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\Rightarrow \Theta(n))
Achtung: Das ist nur eine Idee, ob das möglich ist, weiß ich nicht!!!
LG |
| Jasmalguckenp |
asymptotische Schranke für Rekurrenz
Meine Frage:
Hallo zusammen, ich muss mehrere Aufgaben zu asymptotischen Schranken lösen. Grundsätzlich verstehe ich das Prinzip, bei einer habe ich jedoch ein Problem. Die Rekurrenz lautet:
T(n)=2·T(sqrt(n))+log2n
Im nächsten Schritt muss ich ja a, b und f(n) bestimmen. a und f(n) sind logisch: a = 2 und f(n) = log2n. Mein Problem liegt bei der Angabe von b.
Meine Ideen:
Meine Idee ist, dass b=1 gilt. Wenn ich dann aber n^(logba) berechnen will, klappt das natürlich nicht, da die Basis > 1 sein muss.
Ist der Wert für b vielleicht ein ganz anderer und falls ja, wie komme ich darauf? Oder gibt es für diese Rekurrenz gar keine Schranke (bzw. muss es nicht für jede Rekurrenz eine Schranke geben)?
Über Tipps würde ich mich wirklich sehr freuen 
|
|
|
