Beweisen Sie, dass f + g = O(max{f, g}) gilt.

Question

Hallo ich hab eine Verständnisfrage:

Aufgabe:

Seien \( f, g: \mathbb{N}_{0} \rightarrow \mathbb{N}_{0} \) zwei Funktionen. Man kann aus \( f \) und \( g \) zwei weitere Funktionen namens \( f+g \) und \( \max \{f, g\} \) definieren. Ihre Funktionwerte sind jeweils die Summe bzw. das Maximum der beiden ursprünglichen Funktionswerte, d.h. es gilt für alle \( n \in \mathrm{N}_{0} \) :
\[
(f+g)(n):=f(n)+g(n) \quad \text { und } \quad \max \{f, g\}(n):=\max \{f(n), g(n)\}
\]
Ist z.B. \( f(n):=4 n^{2} \) und \( g(n):=n^{3}, \) so gilt \( (f+g)(n)=n^{3}+4 n^{2} \) sowie
\[
\max \{f, g\}=\left\{\begin{array}{ll}
4 n^{2} & \text { falls } n \leq 4 \\
n^{3} & \text { sonst }
\end{array}\right.
\]
Zeigen Sie, dass dann stets (also nicht nur in diesem Beispiel!) \( f+g=O(\max \{f, g\}) \) gilt.

Wir haben auch gleich die Lösung bekommen, nur verstehe ich sie nicht.

Aufgabe 1: Natürlich ist für alle \( n \in \mathbb{N}_{0} \) stets \( f(n) \) kleiner oder gleich \( \max \{f(n), g(n)\} \) Analog gilt auch \( g(n) \leq \max \{f(n), g(n)\} \) für alle \( n \in \mathbb{N}_{0}, \) so dass wir
\[
\forall n \geq n_{0}: f(n)+g(n) \leq \max \{f(n), g(n)\}+\max \{f(n), g(n)\}=2 \cdot \max \{f, g\}(n)
\]
schliefen können. Mit der Wahl \( n_{0}:=1 \) und \( c:=2 \) erhalten wir somit die Aussage
\[
\begin{array}{l}
\quad \forall n \geq n_{0}:(f+g)(n)=f(n)+g(n) \leq c \cdot \max \{f(n), g(n)\}=c \cdot \max \{f, g\}(n) \\
\text { d.h. es gilt } f+g=O(\max \{f, g\})
\end{array}
\]

Könnte mir bitte jemand erklären wie genau diese Aufgabe funktioniert Schritt für Schritt?

Und was überhaupt mit max{f,g}(n) gemeint ist? Im Skript wurde dieser Ausdruck nie verwendet und ich bin sehr verwirrt.

Mit freundlichen Grüßen

naili

Answer 1

Da der formelle Beweis da ja schon steht, mach ich das ganze mal wörtlich. Erstmal klären, was \(\max(f,g)\). Es ist die Folge, die bei Eingabe von einem \(n\) das größere der beiden Zahlen \(f(n),g(n)\) zurückgibt. Sprich \(\max(f,g)(n)=\max(f(n),g(n))\). Es ist damit klar, dass \(f\leq \max(f,g)\) und \(g\leq \max(f,g)\) (für alle \(n\)) gilt, per Definition kann kein Folgenwert von \(f,g\) größer sein.

Was bedeutet \(a=O(b)\) wörtlich (für zwei Folgen \(a,b\))? Es bedeutet, dass \(a\) für groß genügende \(n\) (ab einem bestimmten Punkt \(n_0\)) kleiner als ein Vielfaches von \(b\) ist (welches Vielfache, gibt das \(c\) an). Wenn \(f(n)\leq\max(f,g)(n)\) für alle \(n\) und \(g(n)\leq\max(f,g)(n)\) auch für alle \(n\) gilt, dann ist natürlich \(f(n)+g(n)\leq 2\cdot\max(f,g)(n)\) für alle \(n\) (das impliziert natürlich: für alle groß genügenden \(n\)). Die Schranke ist ja ein Vielfaches von \(\max(f,g)\), damit bist du fertig. Im letzten Absatz werden die gewonnenen Erkenntnisse in Wirklichkeit nur ganz rigoros in die Definition eingesetzt.

Comments

Erstmal vielen dank für die Erklärung, ich verstehe es glaube ich fast ganz ^^.

"Erstmal klären, was max(f,g).
Es ist die Folge, die bei Eingabe von einem n das größere der beiden Zahlen f(n),g(n) zurückgibt.
Sprich max(f,g)(n)=max(f(n),g(n))."

Okay nur damit ich das jetzt richtig verstanden hab ^^ tut mir leid wenn das sehr dumme Beispiele sind.

Das heißt max(f,g) ist nichts anderes als eine Funktion. Wenn z.B für n = 50 die Funktion f den Funktionswert 4 ausgibt und Funktion g den Funktionswert 8, dann würde max(f,g) das größere von den beiden ausgeben oder? Also die Funktion g mit Funktionswert 8 (in meinem Beispiel).

Deswegen wird auch nicht nur f<max(f,g) und g<max(f,g) (für alle n) sondern das mit "≤" geschrieben,richtig?
Weil in meinem Beispiel wäre ja f<max(f,g)  und g=max(f,g).

Und weil beide f≤max(f,g) und g≤max(f,g) sind ergibt sich addiert:
f + g ≤ max(f,g) + max(f,g) also f + g ≤ 2max (f,g). Das habe ich jetzt glaube ich verstanden, diesen Teil. Vielen dank!

Nur bei diesem Teil (bei den gegebenen Lösungen):

Mit der Wahl n0:=1 und c:=2 erhalten wir somit die Aussage:
\( \forall n \geq n_{0}:(f+g)(n)=f(n)+g(n) \leq c \cdot \operatorname{mnx}\{f(n), g(n)\}=c \cdot \max \{f, g\}(n) \)

verstehe ich nicht ganz wie wir auf n0=1 kommen.

Die c ist ja die Konstante von der O-Formel, richtig (Allgemeine Formel aus dem Skript: g(n) ≤ c · h(n))?

Und diese ist nun c=2 aufgrund der vorherigen Rechnung von der Addition der max(f,g) + max(f,g)?

Wurde die n0=1 nur als Beispiel zur Veranschaulichung gewählt?

Gruß

~naili

---

Nein, lies meine Antwort noch einmal genau. Das \(n_0\) gibt an, was "groß genug" bedeutet. Du willst ja, dass für groß genügende \(n\) etwas bestimmtes gilt, das \(n_0\) sagt genau, ab wann groß genug ist. Da die Ungleichung ja für alle \(n\) gilt, sind alle \(n\) ab \(1\) "groß genug", deshalb \(n_0=1\).

---

Wäre es in diesen Fällen aber nicht immer n0=1? 

Und kommen generell negative Zahlen nicht in Frage, da es ja um das positive Wachstum geht?

Ich verstehe nicht genau was gelten soll für "groß genügende n" und wie man das einfach ablesen konnte/ ausrechnen kann, dass es in diesem Fall n=1 ist.

---

Ah nein ich glaube ich verstehe warum n0=1. Am Anfang steht ja

n ∈ ℕ0. Und da für n=1 schon der erste Unterschied zwischen beiden Funktionen zu sehen ist, nimmt man 1. Da für 0 ja beide Funktionen den gleichen Wert ausgeben.