Lösen von T (n) = 2T (n / 2) + log n mit der Wiederholungsbaummethode

Ich habe Wiederholungsbeziehungen gelöst. Die erste Wiederholungsbeziehung war

$T(n)=2T(n/2)+n$

Die Lösung für dieses Problem kann durch den Master-Satz oder die Wiederholungsbaummethode gefunden werden. Der Wiederholungsbaum wäre ungefähr so:

Die Lösung wäre:

$T(n)=\underbrace{n+n+n+...+n}_{\log_2{n}=k \text{ times}}=\Theta(n \log{n})$

Als nächstes hatte ich folgendes Problem:

$T(n)=2T(n/2)+\log{n}$

Mein Buch zeigt, dass diese Wiederholung nach dem Hauptsatz oder sogar nach einem Substitutionsansatz die Lösung . Es hat dieselbe Struktur wie oben Baum mit dem einzigen Unterschied , dass es bei jedem Aufruf führt Arbeit. Ich bin jedoch nicht in der Lage, den gleichen Ansatz für dieses Problem zu verwenden. $\Theta(n)$ $\log{n}$

recurrence-relation anir
quelle

Der nicht rekursive Begriff der Wiederholungsrelation ist die Arbeit , um Lösungen von Teilproblemen zusammenzuführen. Die Ebene Ihres (binären) Wiederholungsbaums enthält Teilprobleme mit der Größe $k$ $2^k$ , also müssen Sie zuerst die Gesamtarbeit auf der Ebeneund diese Arbeit dann über alle Baumebenen zusammenfassen. $\frac {n}{2^k}$ $k$

Wenn beispielsweise die Arbeit konstant ist , dann ist die gesamte Arbeit auf der Ebene wird $C$ $k$ , und die Gesamtzeit wird durch die folgende Summe angegeben werden: $2^k \cdot C$ $T(n)$

T (n) = \sum_{k = 1}^{\log_{2} n} 2^{k} C = C (2^{\log_{2} n + 1} - 2) = Θ (n)

$T(n) = \sum_{k=1}^{\log_2{n}}2^k C = C(2^{\log_2{n}+1}-2) = \Theta(n)$

Wenn die Arbeit jedoch logarithmisch mit der Problemgröße wächst, müssen Sie die Lösung genau berechnen. Die Serie würde wie folgt aussehen:

T (n) = \log_{2} n + \underset{\log_{2} n times}{\underset{⏟}{2 \log_{2} (\frac{n}{2}) + 4 \log_{2} (\frac{n}{4}) + 8 \log_{2} (\frac{n}{8}) + . . . .}}

$T(n)=\log_2{n}+\underbrace{2\log_2(\frac {n} {2})+4\log_2(\frac {n} {4})+8\log_2(\frac {n} {8}) + ....}_{\log_2{n} \text{ times}}$

Es wird eine ziemlich komplexe Summe sein:

T (n) = \log_{2} n + \sum_{k = 1}^{\log_{2} n} 2^{k} \log_{2} (\frac{n}{2^{k}})

$T(n)=\log_2{n}+\sum_{k=1}^{\log_2{n}}2^k \log_2(\frac {n} {2^k})$

Ich werde vorübergehend und die obige Summierung vereinfachen: $m=\log_2{n}$

\sum_{k = 1}^{m} 2^{k} \log_{2} (\frac{n}{2^{k}}) = = \sum_{k = 1}^{m} 2^{k} (\log_{2} n - k) = = \log_{2} n \sum_{k = 1}^{m} 2^{k} - \sum_{k = 1}^{m} k 2^{k} = = \log_{2} n (2^{m + 1} - 2) - (m 2^{m + 1} - 2^{m + 1} + 2)

$\sum_{k=1}^{m}2^k \log_2(\frac {n} {2^k})=\\=\sum_{k=1}^{m}2^k(\log_2{n}-k)=\\=\log_2{n}\sum_{k=1}^{m}2^k-\sum_{k=1}^{m}k2^k=\\=\log_2{n}(2^{m+1}-2)-(m2^{m+1}-2^{m+1}+2)$

$\sum_{k=1}^{m}k2^k$ $m$ $\log_2{n}$

T (n) = \log_{2} n + 2 n \log_{2} n - 2 \log_{2} n - 2 n \log_{2} n + 2 n - 2

$T(n)=\log_2{n}+2n\log_2{n}-2\log_2{n}-2n\log_2{n}+2n-2$

= 2 n - \log_{2} n - 2 = Θ (n)

$=2n-\log_2{n}-2=\Theta(n)$

QED

HEKTO
quelle

Verdammt, ich habe einen super dummen Fehler gemacht, als ich Fragen gestellt habe. Jetzt korrigiert. Allerdings kann ich jetzt nicht verstehen, wie sich die Sachen in der Serie gegenseitig aufheben:

2^{0} \log_{2} \frac{n}{2^{0}} + 2^{1} \log_{2} \frac{n}{2^{1}} + 2^{2} \log_{2} \frac{n}{2^{2}} + . . . + 2^{\log_{2} n} \log_{2} \frac{n}{2^{\log_{2} n}} = \log_{2} n + 2 \log_{2} \frac{n}{2} + 4 \log_{2} \frac{n}{4} + . . . + n \log_{2} 1

$2^0\log_2\frac{n}{2^0}+2^1\log_2\frac{n}{2^1}+2^2\log_2\frac{n}{2^2}+...+2^{ \log_2{n}}\log_2\frac{n}{2^{ \log_2{n}}}=\log_2{n}+2\log_2{\frac{n}{2}}+4\log_2{\frac{n}{4}}+...+n\log_2{1}$ .. Dies ist die Serie, die Sie sich einfallen lassen, oder? Versuchen mit

n = 8

$n=8$ , Ich habe

\log_{2} 8 + 2 \log_{2} 4 + 4 \log_{2} 2 + 8 \log_{2} 1 = 3 + 4 + 4 = 11

$\log_2{8}+2\log_2{4}+4\log_2{2}+8\log_2{1}=3+4+4=11$ . Whats wrong here?

anir

@anir - Use equality

\log_{2} (\frac{n}{2^{k}}) = \log_{2} n - k

$\log_2(\frac{n}{2^k}) = \log_2 n - k$

HEKTO

I still didn't get how that series collapses to

Θ (n)

$\Theta(n)$ :'¬( Math-noob-here...

anir

@anir - I'll expand my answer

HEKTO

@HEKTO If you solve above equ of comment, you still get nlog(n) ?? I have tried a lot. would you please help me here ?

roottraveller

Lösen von T (n) = 2T (n / 2) + log n mit der Wiederholungsbaummethode

Antworten: