Master Theorem < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:20 Mi 16.01.2013 | | Autor: | bandchef |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
| Aufgabe | Geben Sie einen Ausdruck für die Laufzeit T(n) für jede der folgenden Rekurrenzen an, wenn die Rekurrenz mit einem der drei Fälle des Master Theorems gelöst werden kann. Ansonsten geben Sie an, dass das Master-Theorem nicht angewendet werden kann.
$T(n) = 3T\left( \frac{n}{2} \right) + n^2$ |
Hi Leute!
Laut Aufgabe kann jeder Fall eintreten. Es kann ein Fall passen aber auch, dass kein Fall passt. Das heißt für mich ich muss wohl jeden Fall durchmachen.
Generell gilt: a=3, b=2 und $f(n) = n^2$
1. Fall:
$f(n) \in O\left(n^{log_b(a)-\epsilon}\right)$
$n^2 \in O\left(n^{log_2(3)-\epsilon}\right)$ mit $\epsilon=log_2(3) - 1$ hier ist $\epsilon > 0$
Nun Grenzwertbildung wie in Wikipedia für die obere Schranke angegeben. Ich definiere für die Grenzwertbildung $f(n):=n^2$ und $g(n):=n^1$.
$\Rightarrow 0 \leq \limsup_{n \to \infty} \left(\left| \frac{f(n)}{g(n)} \right|\right) < \infty$
$\Leftrightarrow 0 \leq \limsup_{n \to \infty} \left(\left| \frac{n^2}{n} \right|\right) < \infty$
$\Leftrightarrow 0 \leq \underbrace{\limsup_{n \to \infty} \left(\left| n \right|\right)}_{\to \infty} < \infty$
Widerspruch! Unendlich ist nicht echt kleiner als Unendlich! Also trifft erster Fall nicht zu.
2. Fall:
$f(n) \in \Theta\left(n^{log_b(a)-\epsilon}\right)$
$n^2 \in \Theta\left(n^{log_2(3)}\right)$
Nun Grenzwertbildung wie in Wikipedia für die exakte Scharfe Schranke angegeben. Ich definiere für die Grenzwertbildung $f(n):=n^2$ und $g(n):=n^{log_2(3)}$.
$\Rightarrow 0 \leq \liminf_{n \to \infty} \left(\left| \frac{f(n)}{g(n)} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{f(n)}{g(n)} \right|\right) < \infty$
$\Rightarrow 0 \leq \liminf_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) < \infty$
Hier verstehe ich dann ehrlich gesagt auch die Definition in der Wikipedia nicht! Und zwar: asymptotisch scharfe Schranke, sowohl $f(n) \in O\left(g(n)\right)$ als auch $ g(n) \in \left(f(n)\right)$. Müsste ich dann beim zweiten limes, also den limsup, nicht die Funktion gegeneinander tauschen, so dass es so aussieht: $\Rightarrow 0 \leq \liminf_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{n^{log_2(3)}}{n^2} \right|\right) < \infty$
Ich breche den zweiten Fall hier dann mal (aus Unwissenheit) ab und mache beim dritten Fall weiter.
3. Fall:
1. Bedingung:
$f(n) \in \Theta\left(n^{log_b(a)+\epsilon}\right)$
$n^2 \in \Theta\left(n^{log_2(3)+\epsilon}\right)$ mit $\epsilon = 2- log_2(3)$ hier ist $\epsilon > 0$
Nun Grenzwertbildung wie in Wikipedia für die untere Schranke angegeben. Ich definiere für die Grenzwertbildung $f(n):=n^2$ und $g(n):=n^{n^2}$.
$\Rightarrow 0 \leq \liminf_{n \to \infty} \left(\left| \frac{f(n)}{g(n)} \right|\right) \leq \infty$
$\Leftrightarrow 0 \leq \liminf_{n \to \infty} \left(\left| \frac{n^2}{n^2} \right|\right) \leq \infty$
$\Leftrightarrow 0 \leq \liminf_{n \to \infty} \left(\left| 1 \right|\right)} < \infty$
Ist richtig weil $0 \leq 1 \leq \infty$ gilt.
2. Bedingung:
$\Rightarrow a\cdot f\left( \frac{n}{b} \right) \leq c \cdot f(n)$
$\Leftrightarrow \frac34n^2 \leq c\cdot n^2$ mit $c=\frac34, c<1$
$\Leftrightarrow \frac34n^2 \leq \frac34\cdot n^2$
Da nun beide Bedingungen für den dritten Fall richtig sind, gilt: $T(n) = \Theta(f(n)) = \Theta(n^2)$
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:01 Mi 16.01.2013 | | Autor: | Helbig |
> Geben Sie einen Ausdruck für die Laufzeit T(n) für jede
> der folgenden Rekurrenzen an, wenn die Rekurrenz mit einem
> der drei Fälle des Master Theorems gelöst werden kann.
> Ansonsten geben Sie an, dass das Master-Theorem nicht
> angewendet werden kann.
>
> [mm]T(n) = 3T\left( \frac{n}{2} \right) + n^2[/mm]
>
>
>
>
>
>
> Hi Leute!
>
> Laut Aufgabe kann jeder Fall eintreten. Es kann ein Fall
> passen aber auch, dass kein Fall passt. Das heißt für
> mich ich muss wohl jeden Fall durchmachen.
Richtig.
>
> Generell gilt: a=3, b=2 und [mm]f(n) = n^2[/mm]
>
> 1. Fall:
> [mm]f(n) \in O\left(n^{log_b(a)-\epsilon}\right)[/mm]
> [mm]n^2 \in O\left(n^{log_2(3)-\epsilon}\right)[/mm]
> mit [mm]\epsilon=log_2(3) - 1[/mm] hier ist [mm]\epsilon > 0[/mm]
>
> Nun Grenzwertbildung wie in Wikipedia für die obere
> Schranke angegeben. Ich definiere für die Grenzwertbildung
> [mm]f(n):=n^2[/mm] und [mm]g(n):=n^1[/mm].
>
> [mm]\Rightarrow 0 \leq \limsup_{n \to \infty} \left(\left| \frac{f(n)}{g(n)} \right|\right) < \infty[/mm]
>
> [mm]\Leftrightarrow 0 \leq \limsup_{n \to \infty} \left(\left| \frac{n^2}{n} \right|\right) < \infty[/mm]
>
> [mm]\Leftrightarrow 0 \leq \underbrace{\limsup_{n \to \infty} \left(\left| n \right|\right)}_{\to \infty} < \infty[/mm]
>
> Widerspruch! Unendlich ist nicht echt kleiner als
> Unendlich! Also trifft erster Fall nicht zu.
Falsch! Du hast nur gezeigt, daß die Bedingung für ein bestimmtes [mm] $\epsilon$ [/mm] nicht erfüllt ist. Aber es könnte ja ein anderes [mm] $\epsilon>0$ [/mm] passen! Warum ist die Bedingung des ersten Falls für kein [mm] $\epsilon>0$ [/mm] erfüllt?
>
>
> 2. Fall:
> [mm]f(n) \in \Theta\left(n^{log_b(a)-\epsilon}\right)[/mm]
> [mm]n^2 \in \Theta\left(n^{log_2(3)}\right)[/mm]
>
> Nun Grenzwertbildung wie in Wikipedia für die exakte
> Scharfe Schranke angegeben. Ich definiere für die
> Grenzwertbildung [mm]f(n):=n^2[/mm] und [mm]g(n):=n^{log_2(3)}[/mm].
>
> [mm]\Rightarrow 0 \leq \liminf_{n \to \infty} \left(\left| \frac{f(n)}{g(n)} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{f(n)}{g(n)} \right|\right) < \infty[/mm]
>
> [mm]\Rightarrow 0 \leq \liminf_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) < \infty[/mm]
Hier hast Du die Definition für [mm] $\Theta$ [/mm] von Wikipedia falsch abgeschrieben. Links muß $0 <$ und nicht [mm] $0\le$ [/mm] stehen!
> 3. Fall:
> 1. Bedingung:
> [mm]f(n) \in \Theta\left(n^{log_b(a)+\epsilon}\right)[/mm]
> [mm]n^2 \in \Theta\left(n^{log_2(3)+\epsilon}\right)[/mm]
> mit [mm]\epsilon = 2- log_2(3)[/mm] hier ist [mm]\epsilon > 0[/mm]
Für dieses [mm] $\epsilon$ [/mm] ist die Bedingung erfüllt, da [mm] $n^2\in \Theta(n^2)\,.$
[/mm]
Dies kann man also abkürzen.
>
> Nun Grenzwertbildung wie in Wikipedia für die untere
> Schranke angegeben. Ich definiere für die Grenzwertbildung
> [mm]f(n):=n^2[/mm] und [mm]g(n):=n^{n^2}[/mm].
>
> [mm]\Rightarrow 0 \leq \liminf_{n \to \infty} \left(\left| \frac{f(n)}{g(n)} \right|\right) \leq \infty[/mm]
>
> [mm]\Leftrightarrow 0 \leq \liminf_{n \to \infty} \left(\left| \frac{n^2}{n^2} \right|\right) \leq \infty[/mm]
>
> [mm]\Leftrightarrow 0 \leq \liminf_{n \to \infty} \left(\left| 1 \right|\right)} < \infty[/mm]
>
> Ist richtig weil [mm]0 \leq 1 \leq \infty[/mm] gilt.
>
>
> 2. Bedingung:
>
> [mm]\Rightarrow a\cdot f\left( \frac{n}{b} \right) \leq c \cdot f(n)[/mm]
>
> [mm]\Leftrightarrow \frac34n^2 \leq c\cdot n^2[/mm] mit [mm]c=\frac34, c<1[/mm]
>
> [mm]\Leftrightarrow \frac34n^2 \leq \frac34\cdot n^2[/mm]
>
>
> Da nun beide Bedingungen für den dritten Fall richtig
> sind, gilt: [mm]T(n) = \Theta(f(n)) = \Theta(n^2)[/mm]
Richtig!
Übrigens, wenn [mm] $\lim {f(n)\over g(n)}$ [/mm] existiert, braucht man nicht [mm] $\liminf$ [/mm] bzw. [mm] $\limsup$ [/mm] zu untersuchen, da dann alle drei Zahlen gleich sind, und es meist geradezu trivial ist, den Grenzwert zu bestimmen.
Gruß,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:59 Do 17.01.2013 | | Autor: | bandchef |
> Falsch! Du hast nur gezeigt, daß die Bedingung für ein bestimmtes [mm] \epsilon [/mm] nicht erfüllt ist. Aber es könnte ja ein anderes [mm] \epsilon>0 [/mm] passen! Warum ist die Bedingung des ersten Falls für kein [mm] \epsilon>0 [/mm] erfüllt?
Also der eigentliche Exponent liegt ja irgendwas bei 1,585. Da der eigentliche Exponenten schon kleiner als der Exponent von f(n) ist, und nun auch noch [mm] \epsilon [/mm] >0 abgezogen werden MUSS, kann es kein passendes [mm] \epsilon [/mm] > 0 geben. Richtig argumentiert? Wie aber schreibe ich diesen Satz etwas kürzer und mathematischer?
$ [mm] \Rightarrow [/mm] 0 [mm] \leq \liminf_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) [/mm] < [mm] \infty [/mm] $
Ok, da hast du natürlich Recht. Nicht gescheit aufgepasst. Hier dann also nochmal die Zeile richtig:
$ [mm] \Rightarrow [/mm] 0 < [mm] \liminf_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) [/mm] < [mm] \infty [/mm] $
Aber wie ich in meiner letzten Antwort schon geschrieben hatte, weiß ich mit dieser Definition nix anzufangen, weil ja irgendwie über die gleiche Funktion der jeweilige Grenzwert gebildet wird und es ja dann klar ist, dass da das gleich Ergebnis rauskommt... Irgendwie kapier ich einfach diese Zeile an sich nicht...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:29 Do 17.01.2013 | | Autor: | Helbig |
> > Falsch! Du hast nur gezeigt, daß die Bedingung für ein
> bestimmtes [mm]\epsilon[/mm] nicht erfüllt ist. Aber es könnte ja
> ein anderes [mm]\epsilon>0[/mm] passen! Warum ist die Bedingung des
> ersten Falls für kein [mm]\epsilon>0[/mm] erfüllt?
>
> Also der eigentliche Exponent liegt ja irgendwas bei 1,585.
> Da der eigentliche Exponenten schon kleiner als der
> Exponent von f(n) ist, und nun auch noch [mm]\epsilon[/mm] >0
> abgezogen werden MUSS, kann es kein passendes [mm]\epsilon[/mm] > 0
> geben. Richtig argumentiert? Wie aber schreibe ich diesen
> Satz etwas kürzer und mathematischer?
Für jedes positive [mm] $\epsilon$ [/mm] ist [mm] $\alpha [/mm] = [mm] \log_2(3)-\epsilon [/mm] < [mm] 2\,,$ [/mm] und für [mm] $\alpha [/mm] < 2 $ ist [mm] $n^2\notin O\left(n^\alpha\right)\,.$
[/mm]
>
>
>
> [mm]\Rightarrow 0 \leq \liminf_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) < \infty[/mm]
>
> Ok, da hast du natürlich Recht. Nicht gescheit aufgepasst.
> Hier dann also nochmal die Zeile richtig:
>
> [mm]\Rightarrow 0 < \liminf_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) < \infty[/mm]
>
> Aber wie ich in meiner letzten Antwort schon geschrieben
> hatte, weiß ich mit dieser Definition nix anzufangen, weil
> ja irgendwie über die gleiche Funktion der jeweilige
> Grenzwert gebildet wird und es ja dann klar ist, dass da
> das gleich Ergebnis rauskommt... Irgendwie kapier ich
> einfach diese Zeile an sich nicht...
Da die Folge konvergiert, ist [mm] $\limsup [/mm] = [mm] \liminf [/mm] = [mm] \lim\,.$ [/mm] Und dieser Limes muß $>0$ und [mm] $<\infty$ [/mm] sein!
Grüße,
Wolfgang
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:26 Do 31.01.2013 | | Autor: | bandchef |
Sorry, wenn ich mich nach so langer Zeit noch zu diesem Thema melde aber ich bin heute hier wieder hängen geblieben:
$ [mm] \Rightarrow [/mm] 0 < [mm] \liminf_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) [/mm] < [mm] \infty [/mm] $
Da diese Folge nun konvergiert kann ich also gleich den normalen Limes bilden. Das ist aber nun ein Problem für mich, da ich beim Limesbilden die Regel von l'Hospital anwenden muss und ich nicht weiß ob die Differenzierung vom Nenner stimmt...:
$ [mm] \Rightarrow [/mm] 0 < [mm] \liminf_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) [/mm] < [mm] \infty [/mm] $
[mm] $\overbrace{\Leftrightarrow}^{=l'H} [/mm] 0 < [mm] \liminf_{n \to \infty} \left(\left| \frac{2n}{log_2(3) \cdot n^{log_2(3)-1}} \right|\right) [/mm] < [mm] \infty [/mm] $
[mm] $\overbrace{\Leftrightarrow}^{=l'H} [/mm] 0 < [mm] \liminf_{n \to \infty} \left(\left| \frac{2n}{log_2(3) \cdot (log_2(3)-1) \cdotn^{log_2(3)-2}} \right|\right) [/mm] < [mm] \infty [/mm] $
Das ist doch jetzt falsch, weil das ganze gegen 0 geht und das laut Definition nicht sein darf. Aber ist die Differenzierung im Nenner wirklich richtig?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:19 Do 31.01.2013 | | Autor: | Helbig |
> Sorry, wenn ich mich nach so langer Zeit noch zu diesem
> Thema melde aber ich bin heute hier wieder hängen
> geblieben:
>
> [mm]\Rightarrow 0 < \liminf_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) \leq \limsup_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) < \infty[/mm]
>
> Da diese Folge nun konvergiert kann ich also gleich den
> normalen Limes bilden. Das ist aber nun ein Problem für
> mich, da ich beim Limesbilden die Regel von l'Hospital
> anwenden muss und ich nicht weiß ob die Differenzierung
> vom Nenner stimmt...:
>
> [mm]\Rightarrow 0 < \liminf_{n \to \infty} \left(\left| \frac{n^2}{n^{log_2(3)}} \right|\right) < \infty[/mm]
>
> [mm]\overbrace{\Leftrightarrow}^{=l'H} 0 < \liminf_{n \to \infty} \left(\left| \frac{2n}{log_2(3) \cdot n^{log_2(3)-1}} \right|\right) < \infty[/mm]
>
> [mm]\overbrace{\Leftrightarrow}^{=l'H} 0 < \liminf_{n \to \infty} \left(\left| \frac{2n}{log_2(3) \cdot (log_2(3)-1) \cdotn^{log_2(3)-2}} \right|\right) < \infty[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
>
> Das ist doch jetzt falsch, weil das ganze gegen 0 geht und
> das laut Definition nicht sein darf. Aber ist die
> Differenzierung im Nenner wirklich richtig?
Nein! Da hast Du dich verrechnet. Im Zähler auch. (Ableitung von 2n ist 2 und nicht 2n), im Nenner fehlt noch ein Faktor n vor dem letzten Logarithmus.
Aber ganz abgesehen davon: L'Hospital geht nur bei lim nicht bei limsup oder liminf. Es mag den einen oder anderen Korrektor irritieren, wenn Du liminf statt lim schreibst.
Und zweitens: Mit L'Hospital wird es komplizierter als nötig! Du weißt, daß $\log_2 3 < 2$ ist. Damit strebt ${n^{2-\log_2 3} \to \infty\,.$ (Weil der Exponent positiv ist).
Gruß,
Wolfgang
|
|
|
|
