Groß Oh Notation!

04.12.2008, 11:51	karllson	Auf diesen Beitrag antworten »
Groß Oh Notation! Hey folks Ich habe mal wieder ein Problem - ****** Mathe... Aufgabe: Es seien $\begin{eqnarray} f1, f2, g1, g2 : \mathbb N \rightarrow \mathbb R \end{eqnarray}$ Funktionen mit $\begin{eqnarray} f1 = O(g1(n)) \end{eqnarray}$ und $\begin{eqnarray} f2 = O(g2(n)) \end{eqnarray}$ . Man beweise: a) $\begin{eqnarray} (f1 + f2)(n) = O(max\{ \|g1(n)\|, \|g2(n)\| \} ) \end{eqnarray}$ b) $\begin{eqnarray} (f1f2)(n) = O(g1(n)g2(n)) \end{eqnarray}$ Meine Ideen, der Übersicht wegen, gleich im Antwortthread. Danke fürs Lesen... Grüße
04.12.2008, 12:21	karllson	Auf diesen Beitrag antworten »
RE: Groß Oh Notation! So also meine Ideen, a) also f(n) ist ja so definiert: es gibt ein $\begin{eqnarray} C\geq 0 \end{eqnarray}$ so dass $\begin{eqnarray} \|f(n)\|\leq C\|g(n)\| \end{eqnarray}$ für alle $\begin{eqnarray} n \geq n0 \end{eqnarray}$ Soweit so gut. Da man ja nur an "großen" n interessiert ist, leuchtet mir auch ein, dass die Summe der beiden Funktionen nach oben abgeschätzt wird durch das Maximum ihrer "Einzelfunktionen". (f1 + f2)(n) ist also in jedem Fall Element von O(g(n)) wenn das n maximal g1(n) und g2(n) ist. Mir ist also klar, dass dem so ist. Aber ich weiß nicht wie, oder besser gesagt, in welcher Form ich das beweisen soll - quasi der "Kniff" b) Das Produkt von f1 und f2 ist sicher Element O(g1(n)g2(n)) das es auch eine Konstante C gibt die o.G. erfüllt. Mein Problem nur, wie soll ich das beweisen. Bin um jeden Tipp dankbar! Danke fürs Lesen! Grüße!
04.12.2008, 13:07	DGU	Auf diesen Beitrag antworten »
Kleiner Korrektur zu a): f(n) Element O (g(n)) ist so definiert: Es gibt ein C usw... Beweisen kannst du die gewünschte Aussage durch Angabe eines C, sodass \| f1 + f2\| kleiner gleich C * \| max(g1,g2) \| für hinreichend große n. Nach Annahme existieren C1 und C2 so, dass \|f1\| kleiner gleich C1 * \|g1\| etc. Wie müsste dann C gewählt werden? Tip: Wähle C "ähnlich" zu max(g1,g2).
05.12.2008, 10:34	karllson	Auf diesen Beitrag antworten »
Hmm, erstmal danke für die Antwort. Ich bin jetzt soweit: (f1 + f2)(n) = O(g1(n)) + O(g2(n)) \|f1 + f2\| $\begin{eqnarray} \leq \end{eqnarray}$ C * \|g1(n)\| + C * \|g2(n)\| Jetzt muss man nur irgendwie auf das Maximum kommen. Kann man C= Maximum (g1)(g2) setzen? Dann hätte man aber: max(g1(n)) * (g1(n)) + ... Also mir ist klar, dass f1 + f2 höchstens so groß sein kann wie das Maximum der Summe von g1 und g2. Aber wie das C wählen? Kann man C=1 wählen, so dass es wegfällt, und dann einfach sagen dass f1+f2 auf jeden Fall kleiner gleich g1 und g2 ist, wenn die das Maximale sind? Überlegungen in Ordnung, oder nen harken? Danke fürs lesen!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »