Beweise der O-Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:10 Sa 14.02.2009 | | Autor: | bonanza |
| Aufgabe 1 | Zeigen Sie mit Hilfe der Definition der O-Notation:
[mm] \bruch{2}{n}\summe_{i=1}^{n+1}i \in [/mm] O(n) |
| Aufgabe 2 | Zeigen Sie oder widerlegen Sie mit Hilfe der Definiton der O-Notation und geben Sie, falls die Aussage gilt ein c [mm] \in [/mm] R und ein [mm] n_0 \in [/mm] N an.
[mm] a)n^2+5n-7 \in [/mm] O(n)
[mm] b)n*log_2(n) \in O(n^2)
[/mm]
[mm] c)n^3 \in O(n^2) [/mm] |
Nabend,
Ich habe mich mal an den Aufgaben versucht, bin mir allerdings sowohl bei der Rechnung, als auch bei der formalen Schreibweise ziemlich unsicher. Ich wär dankbar, wenn mal jmd. drüberschauen könnte ;)
Aufgabe1:
[mm] \bruch{2}{n}\summe_{i=1}^{n+1}i [/mm] = [mm] \bruch{2*(n+1)(n+2)}{2n} [/mm] = [mm] \bruch{n^2+3n+2}{n}
[/mm]
=> [mm] \bruch{n^2+3n+2}{n} \le [/mm] c*n
=> [mm] \bruch{1+3/n+2/n^2}{1} \le [/mm] c
=> 1 [mm] \le [/mm] c für [mm] n\to\infty
[/mm]
Ich wähle dann c=1.
Berechnug von [mm] n_0 [/mm] (hier bin ich mir besonders unsicher):
Ich habe mir gedacht, dass damit das für c=1 erfüllt ist, müsste [mm] \bruch{3}{n}+\bruch{2}{n^2} [/mm] = 0 sein.
=> [mm] n=-\bruch{2}{3}
[/mm]
Aber was wäre jetzt mein [mm] n_0 [/mm] ? Oder soll mir das negative sagen, dass es generell gilt für n>0? oder bin ich bei der Überlegung schon komplett auf den Holzweg ? (Eine Hinweis wie ich [mm] n_0 [/mm] generell berechne, wäre sehr hilfreich)
Aufgabe2:
a)
Behauptung: [mm] n^2+5*n-7\lec*n^2
[/mm]
=> [mm] \bruch{1+5/n-7/n^2}{1}\to [/mm] 1 für [mm] n\to\infty
[/mm]
=> [mm] 1\lec
[/mm]
Ich wähle c=1.
Bedingung für [mm] n_0: \bruch{5}{n}-\bruch{7}{n^2}=0
[/mm]
=> [mm] n=\bruch{7}{5} [/mm] => [mm] n_0 \ge \bruch{7}{5}
[/mm]
=> Behauptung korrekt
b)
Behauptung: [mm] n*log_2(n)\lec*n^2 [/mm]
=> [mm] \bruch{log_2(n)}{n} \to1 [/mm] für [mm] n\to\infty [/mm] => [mm] 1\lec
[/mm]
Ich wähle c=1.
Bedingung für [mm] n_0:
[/mm]
[mm] \bruch{log_2(n)}{n} [/mm] = 1
Aber wie kann ich das auflösen? :-/
c)
Behauptung: [mm] n^3 \le c*n^2
[/mm]
=> n [mm] \le [/mm] c Widerspruch
=> Behauptung gilt nicht.
Vielen Vielen dank schonmal im voraus !
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:08 So 15.02.2009 | | Autor: | bazzzty |
> Aufgabe1:
>
> [mm]\bruch{2}{n}\summe_{i=1}^{n+1}i[/mm] = [mm]\bruch{2*(n+1)(n+2)}{2n}[/mm]
> = [mm]\bruch{n^2+3n+2}{n}[/mm]
> => [mm]\bruch{n^2+3n+2}{n} \le[/mm] c*n
> => [mm]\bruch{1+3/n+2/n^2}{1} \le[/mm] c
> => 1 [mm]\le[/mm] c für [mm]n\to\infty[/mm]
> Ich wähle dann c=1.
Vorsicht! Der Grenzwert geht zwar gegen 1, aber von oben. Du wirst kein [mm]n_0[/mm] finden, für das [mm]1+3/n+2/n^2\le 1[/mm] gilt. Sei großzügig! Wenn es mit c=1 knapp wird, warum dann nicht c=6 wählen? dann ist alles ganz einfach: [mm]1+3/n+2/n^2\le 6[/mm] gilt doch für alle [mm]n[/mm], also ab [mm]n_0=1[/mm]. Im O-Kalkül ist das erlaubt: Konstanten grob abschätzen!
> Berechnug von [mm]n_0[/mm] (hier bin ich mir besonders unsicher):
> Ich habe mir gedacht, dass damit das für c=1 erfüllt ist,
> müsste [mm]\bruch{3}{n}+\bruch{2}{n^2}[/mm] = 0 sein.
> => [mm]n=-\bruch{2}{3}[/mm]
> Aber was wäre jetzt mein [mm]n_0[/mm] ? Oder soll mir das negative
> sagen, dass es generell gilt für n>0? oder bin ich bei der
> Überlegung schon komplett auf den Holzweg ? (Eine Hinweis
> wie ich [mm]n_0[/mm] generell berechne, wäre sehr hilfreich)
Hab ich ja schon, aber ein kleiner Hinweis noch: Du darfst aus Ungleichungen nicht einfach Gleichungen machen und dann hoffen, dass die Richtung schon stimmt. Du suchst ein
[mm]n_0[/mm] so dass für alle [mm]n\geq n_0[/mm]
[mm]1+\bruch{3}{n}+\bruch{2}{n^2} \stackrel{!}\leq 1[/mm]. Das ist äquivalent zu [mm][mm] n\stackrel{!}\leq-\bruch{2}{3}[/mm] [mm], bedeutet also, dass [mm]c=1[/mm] generell nichts wird.
> Aufgabe2:
> a)
> Behauptung: [mm]n^2+5*n-7\le c*n^2[/mm]
In der Aufgabe steht O(n)? Was willst Du zeigen?
> => [mm]\bruch{1+5/n-7/n^2}{1}\to[/mm] 1 für [mm]n\to\infty[/mm]
> => [mm]1\le c[/mm]
> Ich wähle c=1.
Leider der gleiche Fehler. Du behauptest also, es gibt ein [mm]n_0[/mm], so dass für alle [mm]n>n_0[/mm] gilt [mm]5n-7\le 0[/mm]. Vergiss bitte die Grenzwerte. Das kann man nicht zeigen, das gilt wieder nur für alle [mm]n \le 7/5[/mm]. Hier helfen auch Proberechnungen!
> Bedingung für [mm]n_0: \bruch{5}{n}-\bruch{7}{n^2}=0[/mm]
Bitte keine Gleichungen aus Ungleichungen machen!
> =>
> [mm]n=\bruch{7}{5}[/mm] => [mm]n_0 \ge \bruch{7}{5}[/mm]
> => Behauptung
> korrekt
Leider nicht. Prüf doch mal nach! Gilt
[mm]n^2+5*n-7\le c*n^2[/mm] für n=3 und c=1?
An dem Beispiel kann man aber super sehen, wie man sich das Leben einfacher macht, wenn man etwas großzügiger arbeitet (und ganz ohne Grenzwerte, die sollte man nur im äußersten Notfall verwenden!). Immer im Kopf behalten: Sowohl [mm] n_0 [/mm] als auch c darf man beliebig hoch wählen, wenns einem hilft!
Trick 1: Alle positiven Glieder links auf höchste Potenz bringen, das wird nur größer
[mm]n^2+5*n-7\le 6n^2-7[/mm] (wir nutzen nur [mm]n\le n^2[/mm])
Trick 2: Alle negative Glieder durch hohes [mm] n_0 [/mm] loswerden.
Für [mm]n>7[/mm]:[mm]6n^2-7\le 5n^2[/mm] (wir nutzen [mm]n^2\ge 7[/mm] für [mm]n\ge 7[/mm])
Und fertig. Manchmal muß man rechts ähnlich vorgehen (aber nach unten abschätzen), hier sind wir fertig: c=5, [mm] n_0=8 [/mm] reicht. Das ist nicht besonders knapp, aber knapp muss es nicht sein.
>
> b)
> Behauptung: [mm]n*log_2(n)\le c*n^2[/mm]
Das kannst Du besser ohne Grenzwerte! Für [mm]n>2[/mm] ist [mm]\log_2(n)\leq n[/mm] und der Rest geht ganz von selbst!
> c)
> Behauptung: [mm]n^3 \le c*n^2[/mm]
> => n [mm]\le[/mm] c Widerspruch
> => Behauptung gilt nicht.
Ja, das stimmt so.
|
|
|
|
