www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Algorithmen und Datenstrukturen" - Laufzeitanalyse
Laufzeitanalyse < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Laufzeitanalyse: Tipp
Status: (Frage) beantwortet Status 
Datum: 14:41 Di 19.04.2011
Autor: Kampfkekschen

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

        
Bezug
Laufzeitanalyse: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Laufzeitanalyse: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:34 Di 19.04.2011
Autor: Kampfkekschen

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



Bezug
                        
Bezug
Laufzeitanalyse: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                                
Bezug
Laufzeitanalyse: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:01 Mi 20.04.2011
Autor: Kampfkekschen

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ß

Bezug
                                        
Bezug
Laufzeitanalyse: Antwort
Status: (Antwort) fertig Status 
Datum: 13:24 Mi 20.04.2011
Autor: kamaleonti

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

Bezug
                                                
Bezug
Laufzeitanalyse: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:08 Mi 20.04.2011
Autor: Kampfkekschen

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

Bezug
                                                        
Bezug
Laufzeitanalyse: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                                                
Bezug
Laufzeitanalyse: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 23:31 Mi 20.04.2011
Autor: 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]
also gibt es keine konstanten [mm] c_1 [/mm] und [mm] c_2? [/mm]

Bezug
                                                                        
Bezug
Laufzeitanalyse: Antwort
Status: (Antwort) fertig Status 
Datum: 07:59 Do 21.04.2011
Autor: schachuzipus

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


Bezug
                                                                
Bezug
Laufzeitanalyse: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 08:00 Do 21.04.2011
Autor: 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


Bezug
                                                                        
Bezug
Laufzeitanalyse: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                                                                
Bezug
Laufzeitanalyse: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:05 Sa 23.04.2011
Autor: Kampfkekschen

Okay, danke für die tolle Hilfe!!

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Algorithmen und Datenstrukturen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]