 asymptotische Schranke für Rekurrenz |
|
|
| 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 
|
|
25.05.2016 21:38 |
|
|
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
 |
|
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
|
|
|
26.05.2016 17:29 |
|
|
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
Ups, da stimmt 
|
|
|
26.05.2016 22:14 |
|
|
|
