master theorem

10.05.2015, 15:33	Auf diesen Beitrag antworten »
colx	master theorem Meine Frage: Geben sie für die folgenden Rekursionsgleichungen(mit Begründung) an,ob diese mit dem Master-Theorem gelöst werden können.Falls dies der Fall ist,geben sie auch die resultierende Komplexitätsklasse an. $[latex]a) T(n)= 16\cdot{}T(\frac{n}{4})+72n^{\sqrt{2}}[/latex]$ $[latex]b) T(n)= 27\cdot{}T(\frac{n}{9})+n^2+n^{\sqrt{2}}[/latex]$ $[latex]c) T(n)= 16\cdot{}T(\frac{n}{4})+\frac{n^3+2n}{n}[/latex]$ $[latex]d) T(n)= 4\cdot{}T(\frac{n}{4})+n\cdot{}log_{2}(n)[/latex]$ Meine Ideen: $[latex]a) T(n)= 16\cdot{}T(\frac{n}{4})+72n^{\sqrt{2}}[/latex]$ und und mit $[latex]E=log_{c}b= 2[/latex]$ und $[latex]n^{\sqrt{2}} < n^2 \Rightarrow 72n^{\sqrt{2}} \in (n^{2-\epsilon}) \Rightarrow T(n) \in \Theta(n^2) [/latex]$ $[latex]b) T(n)= 27\cdot{}T(\frac{n}{9})+n^2+n^{\sqrt{2}}[/latex]$ und und mit $[latex]E=log_{c}b= \frac{3}{2}[/latex]$ außerdem $[latex]n^2+n^{\sqrt{2}}=n^{\frac{5}{2}}[/latex]$ und $[latex]n^{\frac{5}{2}}> n^{\frac{3}{2}}[/latex]$ deshalb $[latex]b \cdot{}f(\frac{n}{c})[/latex]$ und ich bei der irgendwie nicht weiter $[latex]c) T(n)= 16\cdot{}T(\frac{n}{4})+\frac{n^3+2n}{n}[/latex]$ und und mit $[latex]E=log_{c}b= 2 [/latex]$ und $[latex] \frac{n^3+2n}{n}= n^2+2 \Rightarrow n^2+2 \in \Theta(n^2) \Rightarrow T(n) \in \Theta(n^2\cdot{}log(n)) [/latex]$ bei der d hab ich keinen plan :/

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »