Asymptotische Schranken < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:03 So 18.03.2012 | | Autor: | tommy987 |
| Aufgabe | Betrachten die folgende as. Gleichungen und zeigen Sie, welche korrekt sind; Beweisen Sie Ihre Aussagen:
8^(ld n) = [mm] \theta(n^3)
[/mm]
[mm] n^2 [/mm] = [mm] O(7^n)
[/mm]
[mm] 2^n [/mm] = [mm] \theta(3^n)
[/mm]
[mm] n^n [/mm] = [mm] \Omega(n!) [/mm] |
Hallo!
1.Meine Frage ist wie ich generell die Gleichung vernüftig beweisen kann.
2. Wie stelle ich eine Beziehung zwischen 8^(ld n) und [mm] n^3 [/mm] her.
3. Kann ich die letzte Glg. folgend beweisen und zwar dass,
(n-1)*(n-2)...(n-n+1) < n*n*.....n
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:09 Mi 21.03.2012 | | Autor: | tommy987 |
Hätte jemand einen Ansatz für mich?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:13 Mi 21.03.2012 | | Autor: | sandp |
> Betrachten die folgende as. Gleichungen und zeigen Sie,
> welche korrekt sind; Beweisen Sie Ihre Aussagen:
>
> 8^(ld n) = [mm]\theta(n^3)[/mm]
> [mm]n^2[/mm] = [mm]O(7^n)[/mm]
> [mm]2^n[/mm] = [mm]\theta(3^n)[/mm]
> [mm]n^n[/mm] = [mm]\Omega(n!)[/mm]
>
> Hallo!
>
> 1.Meine Frage ist wie ich generell die Gleichung vernüftig
> beweisen kann.
> 2. Wie stelle ich eine Beziehung zwischen 8^(ld n) und [mm]n^3[/mm]
> her.
> 3. Kann ich die letzte Glg. folgend beweisen und zwar
> dass,
>
> (n-1)*(n-2)...(n-n+1) < n*n*.....n
>
hey,
so ich zeigs dir mal anhand eines Beispiels:
[mm] 2^n+n^3 \in O(2^n)
[/mm]
eigentlich braucht man hier nichts zu beweisen, da es offensichtlich ist, aber wir machen es mal mit der formalen Definition der Landau Symbole.
Die Definition von O(g) sieht ja so aus:
Seien f,g: [mm] \IN_{0}\to\IN_{0} [/mm] Funktionen
f [mm] \in O(g):\gdw\exists_{c}\exists_{N}\forall_{n\ge N} [/mm] : f(n) [mm] \le [/mm] c*g(n)
ok also müssen wir jetzt nur noch ein c und ein N finden
[mm] 2^n+n^3 [/mm] schätzen wir ersteinmal nach oben ab (für n [mm] \ge [/mm] 10)
[mm] 2^n+n^3 \le 2^n+2^n [/mm] jetzt folgt wenn [mm] 2^n+2^n \in O(2^n) \Rightarrow 2^n+n^3 \in O(2^n)
[/mm]
so jetzt noch das c
[mm] 2^n+2^n [/mm] = [mm] 2^{n+1} [/mm] = [mm] 2*2^n, [/mm] also haben wir jetzt c=2 und N=10
damit haben wir die formale Definition erfüllt.
Jetzt probier es mal bei deinen Aufgaben selbst.
Gruß sandp
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:40 Mi 21.03.2012 | | Autor: | tommy987 |
| Aufgabe | Meine Ergebnisse wären folgende:
1.) Ja und zwar weil 8^ld(n) = n^ld(8) ist
2.) Nein, da ich auf das Ergebnis von [mm] n*2*log_{7}(n) [/mm] <= 7 gekommen bin.
3.)Nein, da ich ein [mm] c_{1} [/mm] von 3 gewählt habe und dort 3^(n+1) < 2^(n) rauskommt.
4.)Nein, da n! = n* (n-1) * (n-2) und somit kleiner als n * n * n... ist. |
Kann man das als vernüftiges Ergebnis stehen lassen?
lg
Thomas
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:37 Mi 21.03.2012 | | Autor: | sandp |
> Meine Ergebnisse wären folgende:
> 1.) Ja und zwar weil 8^ld(n) = n^ld(8) ist
> 2.) Nein, da ich auf das Ergebnis von [mm]n*2*log_{7}(n)[/mm] <= 7
> gekommen bin.
> 3.)Nein, da ich ein [mm]c_{1}[/mm] von 3 gewählt habe und dort
> 3^(n+1) < 2^(n) rauskommt.
> 4.)Nein, da n! = n* (n-1) * (n-2) und somit kleiner als n
> * n * n... ist.
> Kann man das als vernüftiges Ergebnis stehen lassen?
>
> lg
> Thomas
Nein das sieht garnicht gut aus.
Bei 4. ist deine Begründung richtig, aber nach deiner Begründung würde JA folgen.
Ich glaube du hast die Aussagen der einzelnen Landau Symbole noch nicht verstanden.
Bei 4. ist es ja das Landau Symbol f [mm] \in \Omega(g) [/mm] dieses sagt ja aus, dass f nicht wesentlich langsamer wachsen darf als g.
Also darf die Funktion f nur für einen bestimmten Abschnitt langsamer wachsen als g, aber ab einem bestimmten Wert muss die Funktion f dauerhaft über g sein.
Lies dir am besten mal alle Definition der Landau Symbole durch und mache dir klar, worin die Unterschiede liegen.
gruß sandp
|
|
|
|
