Beweis von asymptotischem Wachstum von Funktionen

Question

Aufgabe: Asymptotisches Wachstum von Funktionen

wir hatten letztens das Asymptotische Wachstum von Funktionen besprochen mit der O notation usw.

Jedoch müssen wir jetzt beweisen/widerlegen das bestimme Funktionen in der O notation enthalten sind, aber ich weiß leider überhaupt nicht wie man an solche Aufgaben herangeht.

Es wäre sehr nett wenn es mir jemand erklären könnte.

Aufgabe:

1) Beweisen Sie $f \in \mathcal{O}(g)$ für $f: \mathbb{N} \rightarrow \mathbb{R}_{\geq 0}$ mit $f(n)=\frac{3 n^{3}+n+1}{3+2 n}$ und $g: \mathbb{N} \rightarrow \mathbb{R}_{\geq 0}$ mit $g(n)=n^{2}$.

2) Widerlegen Sie $f \in \mathcal{O}(g)$ für $f: \mathbb{N} \rightarrow \mathbb{R}_{\geq 0}$ mit $f(n)=n(n+1)$ und $g: \mathbb{N} \rightarrow \mathbb{R}_{\geq 0}$ mit $g(n)=n+3$.

Answer 1

Hallo:-)

Ich schreibe mal die ,,übliche" Landau-Definition für groß-O hin:$$\mathcal{O}(g):=\{f:\ \mathbb{N}\rightarrow \mathbb{R}:\ \exists \alpha>0 \ \exists n_0 \in \mathbb{N} \ \forall n\geq n_0:\ \underbrace{0\leq f(n) \leq \alpha \cdot g(n)}_{0\leq f(n) \ \land f(n)\leq \alpha\cdot g(n) } \}$$Du musst also eine Konstante $\alpha>0$ und eine Stelle $n_0 \in \mathbb{N}$ finden, sodass für alle $n\geq n_0$ die Ungleichung $0\leq f(n)\leq \alpha\cdot g(n)$ gilt.

Ich führe das mal bei 1.) vor:

$0\leq f(n)=\frac{3 n^{3}+n+1}{3+2 n}\stackrel{n\geq 2}{\leq} \frac{3n^3+n^3}{3+2n}=\frac{4n^3}{3+2n}\leq \frac{4n^3}{2n}=2n^2=2\cdot g(n)$

Also wähle ich $\alpha=2$ und $n_0=2$. Damit ist $\frac{3 n^{3}+n+1}{3+2 n}\in \mathcal{O}(n^2)$.

Bei 2.) Musst du nur die Definition entsprechend negieren und diese auf 2.) anwenden.

Comments

Danke für die schnelle Antwort,

ich kann jedoch noch nicht ganz nachvollziehen wie du jetzt auf a=2 und n0=2 gekommen bist.

Ich kann auch nicht ganz nachvollziehen wieso du auf einmal das n+1 durch ein n³ ersetzt hast oder eher gesagt wie du darauf kommst.

Wäre echt nett wenn das erklärt wird. :)

---

Kannst du nachvollziehen, dass $n+1\leq n^3$ für alle $n\in \mathbb{N}_{\geq 2}$ gilt?

Bei solchen Abschätzungen sehe ich auch erst am Ende, wie $\alpha$ gewählt werden muss. Die Stelle $n_0$ kann eben durch Zwischenabschätzungen wie zb $n+1\leq n^3$ für alle $n\in \mathbb{N}_{\geq 2}$ kommen. Stelle ich nun aber fest, dass eine weitere Abschätzung ein größeres $n$ erfordert, dann aktualisiere ich es eben mit dem größeren Wert davon, um eben die neuere Abschätzung mit einzuschließen.

---

Ja das sehe ich ein-

Bedeuted das du wählst einfach irgendwas was größer als n+1 ist? Oder du setzt das n so das n³ größer ist als n+1?

Meine zweite Frage wäre dann ob das dann als Beweis zählt, weil mir kommt es so vor als ob man das n größer irgendwas beliebig setzt. d.h. man muss sozusagen ein n finden wo für es geht?

MfG

---

Hier habe ich $n^3$ gewählt, weil sich im weiteren Verlauf der Abschätzung ein $n$ rauskürzt und ich somit etwas mit $n^2$ am Ende erhalte.

Das was ich in der Rechnung gemacht habe, ist das Finden von $\alpha$ und einer Stelle $n_0$ durch passende Abschätzungsansätze-/versuche. Du kannst aber daraus ein Beweis machen, indem du zu Beginn des Beweises ganz dreist sagst, dass du $\alpha=2$ und $n_0=2$ wählst und dann die Abschätzungskette hinschreibst.

In manchen Fällen sieht man auch bei Funktionen, wie diese zu wählen sind und muss keine Abschätzungsversuche durchführen und kann direkt loslegen.

---

Hm, ich verstehe. Also schätze ich ab, solange ich ein passendes Ergebnis bekomme und dann kann ich diesen Wert "ganz dreist" am Anfang des Beweises voraussetzen und ihn zeigen?

Ich könnte ja theoretisch auch das $alpha$ = 3 setzen und es würde immer noch gelten?

Mfg!

---

Ja, das kannst du auch machen, solange du deine Abschätzungen nachvollziehbar machst.

---

Moin,

könntest du mir vielleicht noch mit der Negation und deren Anwendung weiterhelfen.

(Zu Aufg 2)

Ich bin mir nicht sicher ob die Negation korrekt ist:

∀α∈ℝ>=0,n₀∈ℕ:∃n∈ℕ:n<m:f(n)>α·g(n)

MfG

---

Die Quantoren stimmen soweit. Die Bedingung $0\leq f(n)\leq \alpha\cdot g(n)$ hast du jedoch falsch negiert. Hier versteckt sich eine Und-Aussage, die sich so schreiben lässt:

$0\leq f(n) \land f(n)\leq \alpha\cdot g(n)$. Negiert lautet diese:

$0>f(n)\lor f(n)>\alpha\cdot g(n)$. Bei einer Oder-Aussage muss nur eine der beiden Teilaussagen wahr sein, um insgesamt wahr zu sein.

Insgesamt musst du also diese Aussage bei 2.) zeigen:

$$\forall \alpha>0\ \forall n_0\in \mathbb{N}\ \exists n\geq n_0:\quad 0>f(n)\lor f(n)>\alpha\cdot g(n)$$

---

Laut dem Buch habe ich diese Negation von:

$\exists alpha \in \mathbb{R}_{>0}, n0 \in \mathbb{N}: \forall n \in \mathbb{N}: n \geq n0 \Rightarrow n{(n+1)} \leq alpha*(n+3)$

nach:

$\forall alpha \in \mathbb{R}_{>0}, n0 \in \mathbb{N}: \exists n \in \mathbb{N}: n \geq n0 \wedge n{(n+1)} > alpha*(n+3)$ \)

Das heißt es müssen sozusagen beide dieser Aussagen gelten oder nicht?

Ich weiß leider nicht wie ich bei solch eine Aufgabe wieder loslegen, das Thema liegt mir nicht so :/.

MfG!

---

Und wenn das hier richtig ist:

$\forall \alpha>0\ \forall n_0\in \mathbb{N}\ \exists n\geq n_0:\quad 0>f(n)\lor f(n)>\alpha\cdot g(n)$

Wie würde man bei so einer Aufgabe loslegen?

MfG

---

Euer Buch verlangt genau dasselbe, wie meine Version. Du musst in Abhängigkeit von $\alpha>0$ und $n_0\in \mathbb{N}$ ein $n\in \mathbb{N}$ mit $n\geq n_0$ finden, sodass $(n+1)\cdot n>\alpha \cdot (n+3)$ gilt.

---

Würde theoretisch n0=2 und alpha=1 gelten?

Dann würde ich immer einen größeren Wert auf der linken Seite herausbekommen.

Die Frage ist jetzt halt nur wie ich das Zeige oder "Beweise", oder kann ich wieder dreist am Anfang sagen setze n0:=2 und alpha:=1.

Tut mir echt leid für die Umstände.

MfG

---

$n_0=2$ und $\alpha=1$ sind nur ein Beispiel. Aber die Aussage

$\forall \alpha>0\ \forall n_0\in \mathbb{N}\ \exists n\geq n_0:\quad 0>f(n)\lor f(n)>\alpha\cdot g(n)$

gibt nun vor, dass $n_0\in \mathbb{N}$ und $\alpha>0$ beliebig sind, wegen des Allquantors $\forall$. Du kannst diese beiden Werte also nicht kontrollieren. Deine Wahl von $n\in \mathbb{N},\quad n\geq n_0$ ist also erstmal im Allgemeinen von beiden Parametern $n_0\in \mathbb{N}$ und $\alpha>0$ abhängig.

---

Ja, das habe ich verstanden, aber wie zeige ich diese Abhängigkeit?

Ich kann nicht ganz nachvollziehen wie man an solch eine Aufgabe herangeht. Zum Beweisen habe ich es so verstanden, dass man sozusagen den Term soweit umformt in einen Term der größer ist und der den eigentlichen Term dann Asymptotisch beschränkt.

Bei der widerlegung kann ich es leider nicht wirklich nachvollziehen :/

---

Löse doch einfach mal die Ungleichung $n\cdot (n+1)>\alpha\cdot (n+3)$ explizit nach $n$ auf. Für eine Lösung gilt dann

$$n_1>\frac{\alpha-1}{2}+\sqrt{\left(\frac{\alpha-1}{2}\right)^2-3\cdot \alpha}=\frac{\alpha-1+\sqrt{\alpha^2+10\cdot \alpha+1}}{2}$$

Bis hierhin war das Schmierarbeit.

Jetzt wähle ich für die Widerlegung einfach mein $n$ neu durch

$n>\max\left(\alpha,n_0,\frac{\alpha-1+\sqrt{\alpha^2+10\cdot \alpha+1}}{2}\right).$

Daraus kannst du also per Wahl von $n$ sofort

$$n>\frac{\alpha-1+\sqrt{\alpha^2+10\cdot \alpha+1}}{2}$$

folgern. Jetzt formst du diese Ungleichung noch ein wenig um, damit du deine Behauptung erhältst.

---

Hallo,

ich kann leider deiner Rechnung noch nicht so ganz folgen.

Ich glaube sie ist etwas zu fortgeschritten.

Ich habe zwar verstanden das ich das n in abhängigkeit von c wählen muss, aber weiter weiß ich leider nicht.

MfG

---

Ab wo hast du Probleme?

---

Ungefähr da wie man das n passend wählt.

---

Dann schau dir nochmal die negierte Definition an:

$\forall \alpha>0\ \forall n_0\in \mathbb{N}\ \exists n\geq n_0:\quad 0>f(n)\lor f(n)>\alpha\cdot g(n)$

$n\in \mathbb{N}$ ist von $\alpha>0$ und $n_0\in \mathbb{N}$ abhnängig.