Asymptotische Notationen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:05 Do 09.09.2010 | | Autor: | teka |
| Aufgabe | Gegeben sei die Funktion [mm] f:\IN \to \IR^+_0 [/mm] mit [mm] f(n) = n^2 + 2n + 5[/mm].
1. Beweisen Sie [mm] f(n)\in O(n^2)[/mm] (Groß-Oh).
2. Beweisen Sie [mm] f(n)\in \Omega(n)[/mm].
3. Folgt aus [mm] f(n)\in O(n^2)[/mm] und [mm] f(n)\in \Omega(n)[/mm] [mm] f(n)\in \Theta(n^2)[/mm]? |
1. Beweisen Sie [mm] f(n)\in O(n^2)[/mm] (Groß-Oh).
Prinzipiell muss man doch ein [mm] c\in \IN[/mm] und ein [mm] n_0\in \IN[/mm] finden sodass [mm]f(n) \le c * n^2[/mm], da Groß-O die obere Schranke ist.
Mein Ansatz dazu ist:
[mm]\exists c > 0, \exists n_0\in \IN: \forall n \ge n_0[/mm]
[mm]f(n) \le c * n^2[/mm]
[mm]n^2 + 2n + 5 \le c * n^2 | n^2[/mm]
[mm]2n + 5 \le c[/mm]
Damit ist [mm]c = 7[/mm] und [mm]n = 1[/mm]
2. Beweisen Sie [mm] f(n)\in \Omega(n)[/mm].
Analog ist hier zu zeigen wann [mm]f(n) \ge c * n^2[/mm] ist.
Also [mm]n^2 + 2n + 5 \ge c * n^2[/mm].
Meine Lösung dazu wäre [mm]c = 1[/mm] und [mm]n = 1[/mm].
Wie kann ich daraus auf [mm] f(n)\in \Theta(n^2)[/mm] kommen?
Allgemein bin ich noch sehr unsicher, ob ich das Grundprinzip richtig verstanden und die Aufgabe richtig gelöst habe und wuerde gerne eure Meinung dazu hören ;)
Ich bin für alle Anregungen dankbar!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:08 Do 09.09.2010 | | Autor: | felixf |
Moin!
> Gegeben sei die Funktion [mm]f:\IN \to \IR^+_0[/mm] mit [mm]f(n) = n^2 + 2n + 5[/mm].
> 1. Beweisen Sie [mm]f(n)\in O(n^2)[/mm] (Groß-Oh).
> 2. Beweisen Sie [mm]f(n)\in \Omega(n)[/mm].
> 3. Folgt aus
> [mm]f(n)\in O(n^2)[/mm] und [mm]f(n)\in \Omega(n)[/mm] [mm]f(n)\in \Theta(n^2)[/mm]?
>
> 1. Beweisen Sie [mm]f(n)\in O(n^2)[/mm] (Groß-Oh).
>
> Prinzipiell muss man doch ein [mm]c\in \IN[/mm] und ein [mm]n_0\in \IN[/mm]
> finden sodass [mm]f(n) \le c * n^2[/mm]
...fuer alle $n [mm] \ge n_0$ [/mm] ...
> , da Groß-O die obere
> Schranke ist.
Genau.
> Mein Ansatz dazu ist:
>
> [mm]\exists c > 0, \exists n_0\in \IN: \forall n \ge n_0[/mm]
>
> [mm]f(n) \le c * n^2[/mm]
> [mm]n^2 + 2n + 5 \le c * n^2 | n^2[/mm]
> [mm]2n + 5 \le c[/mm]
Was genau tust du hier? Es stimmt so nicht ganz...
Einfacher geht's so: fuer $n [mm] \ge [/mm] 1$ gilt [mm] $n^2 [/mm] + 2 n + 5 [mm] \le n^2 [/mm] + 2 [mm] n^2 [/mm] + 5 [mm] n^2 [/mm] = 8 [mm] n^2$, [/mm] also kannst du [mm] $n_0 [/mm] = 1$ und $c = 8$ waehlen.
> Damit ist [mm]c = 7[/mm] und [mm]n = 1[/mm]
Das stimmt nicht, fuer $n = 1$ ist $f(n) = 8 > 7 [mm] \cdot 1^2$.
[/mm]
> 2. Beweisen Sie [mm]f(n)\in \Omega(n)[/mm].
>
> Analog ist hier zu zeigen wann [mm]f(n) \ge c * n^2[/mm] ist.
Moment. Oben steht [mm] $\Omega(n)$, [/mm] nicht [mm] $\Omega(n^2)$. [/mm] Also musst du $f(n) [mm] \ge [/mm] c n$ fuer $n [mm] \ge n_0$ [/mm] zeigen.
> Also [mm]n^2 + 2n + 5 \ge c * n^2[/mm].
> Meine Lösung dazu wäre [mm]c = 1[/mm]
> und [mm]n = 1[/mm].
Und warum?
> Wie kann ich daraus auf [mm]f(n)\in \Theta(n^2)[/mm] kommen?
Dazu musst du $f(n) [mm] \ge [/mm] c [mm] n^2$ [/mm] fuer $n [mm] \ge n_0$ [/mm] fuer passende $c, [mm] n_0$ [/mm] zeigen.
Aus $f [mm] \in O(n^2)$ [/mm] und $f [mm] \in \Omega(n)$ [/mm] folgt zumindest nicht automatisch, dass $f [mm] \in \Theta(n)$ [/mm] ist; ein Gegenbeispiel ist die Funktion $f(n) = n$. Bei dir funktioniert es aber, aber nicht weil $f [mm] \in \Omega(n)$ [/mm] ist, sondern weil $f [mm] \in \Omega(n^2)$ [/mm] ist.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:02 Do 09.09.2010 | | Autor: | teka |
> > 2. Beweisen Sie [mm]f(n)\in \Omega(n)[/mm].
> >
> > Analog ist hier zu zeigen wann [mm]f(n) \ge c * n^2[/mm] ist.
>
> Moment. Oben steht [mm]\Omega(n)[/mm], nicht [mm]\Omega(n^2)[/mm]. Also musst
> du [mm]f(n) \ge c n[/mm] fuer [mm]n \ge n_0[/mm] zeigen.
Stimmt da hat sich bei mir ein schreibfehler eingeschlichen.
> > Also [mm]n^2 + 2n + 5 \ge c * n^2[/mm].
> > Meine Lösung dazu
> wäre [mm]c = 1[/mm]
> > und [mm]n = 1[/mm].
>
> Und warum?
[mm]n^2 + 2n + 5 \ge n[/mm]
Deswegen [mm]c = 1[/mm] und [mm]n = 1[/mm].
Stimmt das so?
> > Wie kann ich daraus auf [mm]f(n)\in \Theta(n^2)[/mm] kommen?
>
> Dazu musst du [mm]f(n) \ge c n^2[/mm] fuer [mm]n \ge n_0[/mm] fuer passende
> [mm]c, n_0[/mm] zeigen.
Warum muss ich genau das zeigen? Ist das immer so? Denn aus der Definition wird mir das nicht ganz klar. Das wäre doch dann das gleiche wie fuer Groß-O (und ich könnte [mm]f \in \Omega(n)[/mm] vernachlässigen).
> Aus [mm]f \in O(n^2)[/mm] und [mm]f \in \Omega(n)[/mm] folgt zumindest nicht
> automatisch, dass [mm]f \in \Theta(n)[/mm] ist; ein Gegenbeispiel
> ist die Funktion [mm]f(n) = n[/mm]. Bei dir funktioniert es aber,
> aber nicht weil [mm]f \in \Omega(n)[/mm] ist, sondern weil [mm]f \in \Omega(n^2)[/mm]
> ist.
Also warum [mm]f \in \Omega(n^2)[/mm] ist mir klar, folgt daraus dann [mm]f \in \Theta(n^2)[/mm] weil bei Groß-O und Groß-Omega jeweils [mm]n^2[/mm] steht? Irgendwie komm ich da noch nicht mit.
> LG Felix
>
>
Vielen Dank Felix für deine schnelle und gute antwort!
Grüße
Teka
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:41 Fr 10.09.2010 | | Autor: | felixf |
Moin Teka!
> > > 2. Beweisen Sie [mm]f(n)\in \Omega(n)[/mm].
> > >
> > > Analog ist hier zu zeigen wann [mm]f(n) \ge c * n^2[/mm] ist.
> >
> > Moment. Oben steht [mm]\Omega(n)[/mm], nicht [mm]\Omega(n^2)[/mm]. Also musst
> > du [mm]f(n) \ge c n[/mm] fuer [mm]n \ge n_0[/mm] zeigen.
>
> Stimmt da hat sich bei mir ein schreibfehler
> eingeschlichen.
Wo genau? In der Aufgabenstellung? Oder beim $f(n) [mm] \ge [/mm] c [mm] \cdot n^2$ [/mm] hier?
> > > Also [mm]n^2 + 2n + 5 \ge c * n^2[/mm].
> > > Meine Lösung
> dazu
> > wäre [mm]c = 1[/mm]
> > > und [mm]n = 1[/mm].
> >
> > Und warum?
>
> [mm]n^2 + 2n + 5 \ge n[/mm]
> Deswegen [mm]c = 1[/mm] und [mm]n = 1[/mm].
> Stimmt das
> so?
Ja.
> > > Wie kann ich daraus auf [mm]f(n)\in \Theta(n^2)[/mm] kommen?
> >
> > Dazu musst du [mm]f(n) \ge c n^2[/mm] fuer [mm]n \ge n_0[/mm] fuer passende
> > [mm]c, n_0[/mm] zeigen.
>
> Warum muss ich genau das zeigen? Ist das immer so? Denn aus
> der Definition wird mir das nicht ganz klar. Das wäre doch
> dann das gleiche wie fuer Groß-O (und ich könnte [mm]f \in \Omega(n)[/mm]
> vernachlässigen).
Nun, es ist doch laut Definition genau dann $f [mm] \in \Theta(g)$, [/mm] wenn $f [mm] \in [/mm] O(g)$ und $f [mm] \in \Omega(g)$ [/mm] ist. Hier ist $g(n) = [mm] n^2$, [/mm] also musst du $f(n) [mm] \ge [/mm] c [mm] \cdot [/mm] g(n) = c [mm] \cdot n^2$ [/mm] fuer $n [mm] \ge n_0$ [/mm] mit $c, [mm] n_0$ [/mm] passend zeigen.
Bei Gross-O musst du [mm] $\le$ [/mm] und nicht [mm] $\ge$ [/mm] zeigen.
> > Aus [mm]f \in O(n^2)[/mm] und [mm]f \in \Omega(n)[/mm] folgt zumindest nicht
> > automatisch, dass [mm]f \in \Theta(n)[/mm] ist; ein Gegenbeispiel
> > ist die Funktion [mm]f(n) = n[/mm]. Bei dir funktioniert es aber,
> > aber nicht weil [mm]f \in \Omega(n)[/mm] ist, sondern weil [mm]f \in \Omega(n^2)[/mm]
> > ist.
>
> Also warum [mm]f \in \Omega(n^2)[/mm] ist mir klar, folgt daraus
> dann [mm]f \in \Theta(n^2)[/mm] weil bei Groß-O und Groß-Omega
> jeweils [mm]n^2[/mm] steht? Irgendwie komm ich da noch nicht mit.
Ja, siehe oben: $f [mm] \in \Theta(n^2) \Leftrightarrow [/mm] f [mm] \in O(n^2) \wedge [/mm] f [mm] \in \Omega(n^2)$.
[/mm]
Ich hoffe das hilft dir etwas weiter :)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:45 Sa 11.09.2010 | | Autor: | teka |
Super vielen danke Felix!
Jetzt hats endlich klick gemacht bei mir.
Ist ja doch gar nicht so schwer ;)
Grüße
Teka
|
|
|
|
