Laufzeitanalyse < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Beweisen oder widerlegen Sie:
a) [mm] n^2-7n+5= \theta(n [/mm] log n)
b) 5* [mm] log_{10}(n^3)= \theta (log_2 [/mm] n) |
Hallo zusammen,
ich sitze grade an der Aufgabe und weiß noch nicht so richtig wie ich das beweisen kann.
Das [mm] \theta [/mm] dient ja zur Bestimmung der genauen Wachstumsrate.
zu zeigen ist also, dass es Konstanten [mm] c_1,c_2 [/mm] und [mm] n_o [/mm] gibt sodass
a)
[mm] c_1*(n* [/mm] log n) [mm] \le n^2-7n+5 \le c_2*(n*log [/mm] n)
=> [mm] c_1*log [/mm] n [mm] \le [/mm] n -7 [mm] +\bruch{5}{n} \le c_2*log [/mm] n
wie kann ich denn jetzt weiter abschätzen, sodass ich weiß ob es solche konstanten gibt sodass die ungleichung gilt?
b) hier gilt zu zeigen, dass es Konstanten [mm] c_1, c_2,n_0 [/mm] gibt sodass
[mm] c_1*log_2 [/mm] n [mm] \le 5*log_{10}(n^3) \le c_2*log_2 [/mm] n
wollte nun die basis des logarithmus angleichen und bekomme dann
[mm] c_1*log_2 [/mm] n [mm] \le [/mm] 5* [mm] \bruch{log_2(n^3)}{log_2 (10)} \le c_2*log_2 [/mm] n
[mm] c_1 \le [/mm] 5* [mm] \bruch{log_2(n^3)}{log_2(10)} [/mm] * [mm] \bruch{1}{log_2 n} \le c_2
[/mm]
stimmt das soweit und wenn ja, wie muss ich hier weitermachen?
Wäre froh, wenn mir jemand ein bisschen helfen könnte!
Gruß,
Kekschen
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:54 Di 19.04.2011 | | Autor: | rainerS |
Hallo Kekschen!
> Beweisen oder widerlegen Sie:
> a) [mm]n^2-7n+5= \theta(n \log n)[/mm]
> b) [mm]5* \log_{10}(n^3)= \theta (\log_2 n)[/mm]
> Hallo zusammen,
>
> ich sitze grade an der Aufgabe und weiß noch nicht so
> richtig wie ich das beweisen kann.
> Das [mm]\theta[/mm] dient ja zur Bestimmung der genauen
> Wachstumsrate.
> zu zeigen ist also, dass es Konstanten [mm]c_1,c_2[/mm] und [mm]n_o[/mm]
> gibt sodass
> a)
> [mm]c_1*(n*\log n) \le n^2-7n+5 \le c_2*(n*\log n)[/mm]
> => [mm]c_1*\log n \le n -7 +\bruch{5}{n} \le c_2*\log n[/mm]
> wie kann ich denn jetzt weiter abschätzen, sodass ich
> weiß ob es solche konstanten gibt sodass die ungleichung
> gilt?
Überleg dir doch mal, wie n im Vergleich zu [mm] $\log [/mm] n$ verläuft, z.B. indem du [mm] $\bruch{\log n}{n}$ [/mm] anschaust.
>
> b) hier gilt zu zeigen, dass es Konstanten [mm]c_1, c_2,n_0[/mm]
> gibt sodass
>
> [mm]c_1*\log_2 n \le 5*\log_{10}(n^3) \le c_2*\log_2 n[/mm]
> wollte nun die basis des logarithmus angleichen und
> bekomme dann
> [mm]c_1*\log_2 n \le 5* \bruch{\log_2(n^3)}{\log_2 (10)} \le c_2*\log_2[/mm]
> n
> [mm]c_1 \le 5* \bruch{\log_2(n^3)}{\log_2(10)} * \bruch{1}{\log_2 n} \le c_2[/mm]
>
> stimmt das soweit und wenn ja, wie muss ich hier
> weitermachen?
Vergiss nicht die Logarithmengesetze: [mm] $\log(n^3) [/mm] = 3 [mm] \log [/mm] n$.
Viele Grüße
Rainer
|
|
|
| |
|
Danke schonmal für die Antwort
also hab das jetzt nochmal so umgeschrieben
[mm] c_1* \bruch{log n}{n} \le 1-\bruch{7}{n}+\bruch{5}{n^2} \le c_2* \bruch{log n}{n}
[/mm]
der ausdruck [mm] \bruch{log n}{n} [/mm] wird für große n immer kleiner
aber wie gilt mir das jetzt weiter?
bei der b hab ich jetzt deinen tipp umgesetzt und kam auf
[mm] c_1 \le 5*bruch{3*log_2 n}{log_2(10)}* \bruch{1}{log_2 n} \le c_2
[/mm]
[mm] c_1 \le \bruch{15}{log_2(10)} \le c_2
[/mm]
dabei ist dann [mm] \bruch{15}{log_2(10)}=4,515
[/mm]
muss ich jetzt [mm] c_1\le [/mm] 4,515 und [mm] c_2 \ge [/mm] 4,515 wählen?
gruß,
kekschen
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:14 Mi 20.04.2011 | | Autor: | rainerS |
Hallo!
> Danke schonmal für die Antwort
> also hab das jetzt nochmal so umgeschrieben
>
> [mm]c_1* \bruch{log n}{n} \le 1-\bruch{7}{n}+\bruch{5}{n^2} \le c_2* \bruch{log n}{n}[/mm]
>
> der ausdruck [mm]\bruch{log n}{n}[/mm] wird für große n immer
> kleiner
> aber wie gilt mir das jetzt weiter?
Die Aussage soll doch für [mm] $n>n_0$ [/mm] gelten. Der linke und der rechte Term der Ungleichungskette wird immer kleiner, je größer n wird. Was passiert mit dem mittleren Teil?
>
> bei der b hab ich jetzt deinen tipp umgesetzt und kam auf
> [mm]c_1 \le 5*bruch{3*log_2 n}{log_2(10)}* \bruch{1}{log_2 n} \le c_2[/mm]
>
> [mm]c_1 \le \bruch{15}{log_2(10)} \le c_2[/mm]
> dabei ist dann
> [mm]\bruch{15}{log_2(10)}=4,515[/mm]
> muss ich jetzt [mm]c_1\le[/mm] 4,515 und [mm]c_2 \ge[/mm] 4,515 wählen?
Die Zahlen habe ich nicht nachgerechnet, aber sonst richtig.
Viele Grüße
Rainer
|
|
|
| |
|
danke für die antwort...
zu a nochmal :
also wenn n immer größer wird dann werden die beiden äußeren teile der ungleichung immer kleiner und der mittlere teil geht gegen 1!
aber ich weiß immer noch nicht, wie ich jetzt weiter abschätzen kann um zu wissen ob die ungleichung für bestimmte [mm] c_1,c_2 [/mm] und [mm] n_0 [/mm] erfüllt ist oder nicht...
gruß
|
|
|
| |
|
Hallo,
> danke für die antwort...
> zu a nochmal :
> also wenn n immer größer wird dann werden die beiden
> äußeren teile der ungleichung immer kleiner (aber nicht kleiner als Null)und der mittlere teil geht gegen 1!
Richtig, hier ist also ein Widerspruch beim Grenzübergang. Damit ist Aussage a) widerlegt.
> aber ich weiß immer noch nicht, wie ich jetzt weiter
> abschätzen kann um zu wissen ob die ungleichung für
> bestimmte [mm]c_1,c_2[/mm] und [mm]n_0[/mm] erfüllt ist oder nicht...
Du brauchst nichts weiter abzuschätzen.
>
> gruß
LG
|
|
|
| |
|
| Aufgabe | | [mm] c)3^n [/mm] = [mm] \theta(2^n) [/mm] |
danke für die erklärung!
hab eine weitere aufgabe bearbeitet:
zzg:
[mm] \exists c_1,c_2, n_0 [/mm] sodass gilt:
[mm] c_12^n \le 3^n \le c_22^n
[/mm]
-> [mm] \wurzel[n]{c_12^n} \le \wurzel[n]{3^n} \le \wurzel[n]{c_22^n}
[/mm]
[mm] ->\wurzel[n]{c_1}2\le [/mm] 3 [mm] \le \wurzel[n]{c_2}2
[/mm]
da aber jetzt [mm] \wurzel[n]{c_1} [/mm] auch wieder nur eine konstante ist kann ich auch schreiben [mm] c_3:=\wurzel[n]{c_1} [/mm] und [mm] c_4:=\wurzel[n]{c_2}
[/mm]
-> [mm] c_3*2 \le [/mm] 3 [mm] \le c_4*2
[/mm]
ist das soweit schonmal richtig?
gruß,
kekschen
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:04 Mi 20.04.2011 | | Autor: | rainerS |
Hallo Kekschen!
> [mm]c)3^n[/mm] = [mm]\theta(2^n)[/mm]
> danke für die erklärung!
> hab eine weitere aufgabe bearbeitet:
>
> zzg:
> [mm]\exists c_1,c_2, n_0[/mm] sodass gilt:
> [mm]c_12^n \le 3^n \le c_22^n[/mm]
> -> [mm]\wurzel[n]{c_12^n} \le \wurzel[n]{3^n} \le \wurzel[n]{c_22^n}[/mm]
>
> [mm]->\wurzel[n]{c_1}2\le 3 \le \wurzel[n]{c_2}2[/mm]
>
> da aber jetzt [mm]\wurzel[n]{c_1}[/mm] auch wieder nur eine
> konstante ist
Nein, denn es hängt von n ab. Wenn [mm] $n\to\infty$ [/mm] geht [mm]\wurzel[n]{c_1}\to 0[/mm] .
Dividiere die Ungleichungskette durch [mm] $2^n$:
[/mm]
[mm] c_1 \le \left(\bruch{3}{2}\right)^n \le c_2 [/mm]
Was siehst du?
Viele Grüße
Rainer
|
|
|
| |
|
danke schonmal für die antwort!
[mm] c_1 \le \left(\bruch{3}{2}\right)^n \le c_2
[/mm]
für n-> [mm] \infty
[/mm]
geht der mittlere ausdruck [mm] \left(\bruch{3}{2}\right)^n [/mm] gegen [mm] +\infty
[/mm]
also gibt es keine konstanten [mm] c_1 [/mm] und [mm] c_2?
[/mm]
|
|
|
| |
|
Hallo Kampfkekschen,
> danke schonmal für die antwort!
>
> [mm]c_1 \le \left(\bruch{3}{2}\right)^n \le c_2[/mm]
> für n->
> [mm]\infty[/mm]
> geht der mittlere ausdruck [mm]\left(\bruch{3}{2}\right)^n[/mm] gegen [mm]+\infty[/mm] ![[ok]](/images/smileys/ok.gif "[ok]")
> also gibt es keine konstanten [mm]c_1[/mm] und [mm]c_2?[/mm]
Naja, ein [mm]c_1[/mm] kannst du finden, es ist ja [mm]\left(\frac{3}{2}\right)^n[/mm] monoton wachsend, aber es ist unbeschränkt, damit findest du kein [mm]c_2[/mm]
Gruß
schachuzipus
|
|
|
| |
|
Hallo Rainer,
> > da aber jetzt [mm]\wurzel[n]{c_1}[/mm] auch wieder nur eine
> > konstante ist
>
> Nein, denn es hängt von n ab. Wenn [mm]n\to\infty[/mm] geht
> [mm]\wurzel[n]{c_1}\to 0[/mm] .
>
Vertipper?!
[mm]\sqrt[n]{c_1}\to \red{1}[/mm] für [mm]n\to\infty[/mm]
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:51 Fr 22.04.2011 | | Autor: | rainerS |
Hallo!
> Hallo Rainer,
>
>
>
> > > da aber jetzt [mm]\wurzel[n]{c_1}[/mm] auch wieder nur eine
> > > konstante ist
> >
> > Nein, denn es hängt von n ab. Wenn [mm]n\to\infty[/mm] geht
> > [mm]\wurzel[n]{c_1}\to 0[/mm] .
> >
>
> Vertipper?!
>
> [mm]\sqrt[n]{c_1}\to \red{1}[/mm] für [mm]n\to\infty[/mm]
Yep. 
Rainer
|
|
|
| |
|
Okay, danke für die tolle Hilfe!!
|
|
|
|
