Laufzeit von T(n) = 2*T(n/2) + n/log2(n) bestimmen durch Rechnung.

Question

Aufgabe:

Hey Leute ich will von folgender Rekursionsgleichung die Laufzeit bestimmen mithilfe der Rekursionsbaummethode:

T(n) = 2T(\( \frac{n}{2} \)) + \( \frac{n}{log2(n)} \)

Ich habe dafür folgende Formel durch die Rekursionsbaummethode:

T(n) = \( n^{log2(2)} \) + \( \sum\limits_{i=0}^{\log2(n)-1}{2^{i}*f(\frac{n}{2^{i}})} \) , wobei f(n) = \( \frac{n}{log2(n)} \)

Diese Gleichung habe ich immer weiter vereinfacht um auf das Ergebnis zu kommen, aber bin irgendwann stecken geblieben. Hier meine Schritte:

= n + \( \sum\limits_{i=0}^{\log2(n)-1}{2^{i}*\frac{\frac{n}{2^{i}}}{log2(\frac{n}{2^{i}})}} \)

= n + \( \sum\limits_{i=0}^{\log2(n)-1}{\frac{n}{log2(n)-log2(2^{i})}} \)

= n + \( \sum\limits_{i=0}^{\log2(n)-1}{n*\frac{1}{log2(n)-i}} \)

Nun spalte ich i=0 ab und wende das Assoziativitätsgesetz an:

= n +n * (\( \sum\limits_{i=1}^{\log2(n)-1}{\frac{1}{log2(n)}} \) - (\( \sum\limits_{i=1}^{\log2(n)-1}{\frac{1}{i}} \)) + \( \frac{1}{log2(n)} \))

= n + n*(log2(n)*\( \frac{1}{log2(n)} \) + \( \frac{1}{log2(n)} \) - \( \sum\limits_{i=1}^{\log2(n)-1}{\frac{1}{i}} \))

= n + n*(1 - \( \sum\limits_{i=1}^{\log2(n)-1}{\frac{1}{i}} \))

Und ab hier weiß ich nicht mehr weiter... Also diese Summe ist ja die harmonische Reihe. Aber das Minus davor ergibt in meinen Augen keinen Sinn. Daher hoffe ich mir kann jemand sagen wie es weiter geht und das lösen kann. Oder an welcher Stelle ich einen Fehler beim Umformen gemacht habe. Danke schon aml im Voraus. P.S. log2(n) = log₂(n) überall ;)

Comments

T(0) ?

T(1) = T(1/2) ? (n ungerade ?)

---

Stimmt wir haben noch T(1) = 1 gegeben. Sonst aber keine weiteren Infos...

Answer 1

$$sei \quad n=2^m, \quad dann \quad gilt \\ T(2^m) = 2*T(2^{m−1})+2^m*log(2^m) \\ T(2^m) = 2*T(2^{m−1})+2^m*m*log(2) \\ T(2^m)= 2*T(2^{m−1})+m*2^m \\ T(2^m) = 2*\boxed{2*T(2^{m-2})+(m-1)*2^{m-1}}+m*2^m \\ T(2^m) = 4*T(2^{m-2})+(m-1)*2^{m}+m*2^m \\ T(2^m) = 4*\boxed{2*T(2^{m-3})+(m-2)*2^{m-2}}+(m-1)*2^{m}+m*2^m \\ T(2^m) = 8*T(2^{m-3}) +(m-2)*2^{m}+(m-1)*2^{m}+m*2^m \\ \\ allgemein: \\ T(2^m) = 2^m * T(2^0) + 2^m*(1+2+3+...+m) \\ T(2^m) = 2^m * T(1) + 2^m*\frac{m(m+1)}{2} \\ \\ wegen \quad n = 2^m \quad folgt: \\ T(n) = n*T(1) + n*\frac{log(n)(log(n)+1)}{2} \\ T(n) = n*(T(1) + \frac{log(n)(log(n)+1)}{2}) \\ $$