asymptotische Schranke für Rekurrenz

25.05.2016, 21:38	Auf diesen Beitrag antworten »
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


26.05.2016, 17:29	Auf diesen Beitrag antworten »
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]$ $[latex]\Rightarrow a=2, b=2, f(n)=\log_2(n)[/latex]$ Somit ist $[latex]f\in\mathcal{O}(n^{\log_b(a)-\epsilon})[/latex]$ $[latex]\Rightarrow \Theta(n)[/latex]$ Achtung: Das ist nur eine Idee, ob das möglich ist, weiß ich nicht!!! LG
26.05.2016, 17:56	Auf diesen Beitrag antworten »
eulerscheZahl	Für das Mastertheorem braucht man ja als rekursiven Aufruf: $[latex]a\cdot T(\frac n b)[/latex]$ Das scheitert schon daran, dass hier eine Wurzel steht. Du kannst die Wurzel wegsubstituieren. Siehe math.stackexchange.com
26.05.2016, 22:14	Auf diesen Beitrag antworten »
Shizmo	Ups, da stimmt
Anzeige

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »