Informatiker Board | Druckvorschau: asymptotische Schranke für Rekurrenz

Geschrieben von Jasmalguckenp am 25.05.2016 um 21:38:

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 smile

Geschrieben von Shizmo am 26.05.2016 um 17:29:

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 großes Grinsen

$[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

Geschrieben von eulerscheZahl am 26.05.2016 um 17:56:

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