Informatiker Board | Algorithmen

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » master theorem

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

master theorem

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

colx
unregistriert

master theorem

Zitatantwort auf diesen Beitrag erstellen

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

[latex]b= 16[/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]$

[latex]b= 27[/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]$

[latex]b= 16[/latex]

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 :/

10.05.2015 15:33

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » master theorem