hallo,
reicht meine Lösung für diese Aufgabe?
oder muss ich noch per limes zeigen 0 =< inf für f(n) ist?
noch eine Frage, wie ist es wenn man zeigen soll, dass das Master-Theorem nicht anwendbar ist? soll man da alle 3 Fälle zeigen und es dabei eine Widerspruch gibt?
oder zeigen dass es keine c und n_0 gibt?
Danke
Ich weiß nicht, wie genau dein Tutor dich korrigieren wird aber ich persönlich würde:
- die 4. Zeile komplett löschen
- die 5. Zeile korrigieren: Gleichheit zwischen reinpolynomischen Funktionen und gemischten (Polynom-Logarithmus) Funktionen kann es gar nicht geben.
Benutze anstatt dessen die O-Notation:
[tex]n^2\cdot\log(n) \in \Omega \left( n^{1.5+\epsilon} \right)[/tex]
- die 6. Zeile ganz genau nochmals anschauen und mich nochmals überlegen, wo ich durch 9 teilen musst:
[tex]27\cdot \left( \left( \frac{n}{9} \right)^2 \cdot \log \left( \frac{n}{9} \right) \right)[/tex]
Dann bekommst du auch einen vernünftigen Wert für c mit [tex]0<c<1[/tex]
Um zu zeigen, dass das Master-Theorem nicht anwendbar ist, musst du zeigen, dass keiner der 3 Fälle passt bzw. dass du nicht alle Variablen dafür hast.
...der Sieg der Vernunft kann nur der Sieg der Vernünftigen sein
danke erstmal,
also nochmal,
[tex]T(n)=27T(\frac{n}{9})+n^{2}log(n)[/tex]
[tex]a=27 , b=9, f(n)=n^{2}log(n)[/tex]
[tex]log_{b}(a)=log_{9}(27)=1,5[/tex]
1.Bedingung: [tex]f(n)\in \Omega (n^{log_{b}(a+\varepsilon )})[/tex] für ein [tex]\varepsilon >0[/tex]
[tex]n^{2}log(n)\in \Omega (n^{1,5+\varepsilon})[/tex]
für [tex]\varepsilon>0[/tex] ist [tex]n^{2}log(n)\in \Omega (n^{2,5})[/tex] also wahre Aussage
2.Bedingung: [tex]af(\frac{n}{b})\leqslant c\cdot f(n)[/tex]
[tex]27((\frac{n}{9})^{2} log(\frac{n}{9}))\leqslant c\cdot n^{2}log(n)[/tex]
[tex]\Leftrightarrow[/tex]
[tex]\frac{1}{3} n^{2}log(\frac{n}{9}) \leqslant c\cdot n^{2}log(n)[/tex]
wähle [tex]c=\frac{1}{3}[/tex]
für alle [tex]n\geq 1 : \frac{1}{3}n^{2}log(\frac{n}{9})\leq \frac{1}{3}n^{2}log(n)[/tex]
[tex]\Rightarrow T(n)\in \Theta (n^{2,5})[/tex]
oder
[tex]\Rightarrow T(n)\in \Theta (n^{2}log(n))[/tex]
?
Danke
ich tendiere zu [tex]\Rightarrow T(n)\in \Theta (n^{2}log(n))[/tex]
Immer gerne.
für [tex]\varepsilon=1>0[/tex]
Also:
[tex]\Rightarrow T(n)\in \Theta (n^{2}log(n))[/tex]
...der Sieg der Vernunft kann nur der Sieg der Vernünftigen sein
Herzlichen Dank.
ich werde dann eine Aufgabe rein stellen bei dem das Master-Theorem nicht anwendbar ist hoffe schaust auch da rein
Vielen Dank für die Hilfe!
Pfefferspray legal