Wikia

Matheaufgaben

0 Diskussion

Algo

AllgemeinBearbeiten

$\mathcal{O}(h(n))$ ist die Menge aller Funktionen die nicht wesentlich schneller wachsen als $h (n)$ [obere Schranke].

$f (n)$ und $g (n)$ sind Elemente von $\mathcal{O}(h(n))$ . Also praktisch Funktionen, die auf unterschiedliche Art mit n umgehen [z.b. $f (n) = n$ und $g (n) = n / 2$ ], jedoch nicht wesentlich schneller wachsen als $h (n)$ .

Somit: $h (n) > = f (n)$ und $h (n) > = g (n)$ Nun spielt es keine Rolle, wie f und g mit n umgehen, da es nichts an der Wachtstumsrate ändert. (Die Wachtstumsrate ist nicht von konstanten Faktoren [wie z.B. $n / 2$ ] anhängig.)

Definition:
$f\left(n\right) \in \mathcal{O}(h(n)) \leftrightarrow \exists c \exists n_{0} \forall n > n_{0} : |f\left(n\right)| \le c \cdot |h\left(n\right)|$

Aufgabe 1Bearbeiten

Zu zeigen:
$f, g \in \mathcal{O}(h(n)) \Rightarrow f+g \in \mathcal{O}(h(n))$

Beweis:
Offenbar gilt: $\exists c_{k} \exists n_{k} \forall n > n_{k} : |f\left(n\right)| \le c_{k} \cdot |h\left(n\right)| \land |g\left(n\right)| \le c_{k} \cdot |h\left(n\right)|$
mit: $\!\,c_{k} = max(c_{0}, c_{1})$ und $\!\,n_{k} = max(n_{0}, n_{1})$
somit: $|f(n)+g(n)| \le 2 * c_{k} \cdot |h(n)|$

Aufgabe 2Bearbeiten

Zu zeigen:
$f, g \in \mathcal{O}(h(n)) \Rightarrow f*g \in \mathcal{O}(h(n))$

Beweis:
sei $\!\,f(n) = g(n) = n \in O(n)$ , dann ist $\!\,f(n) * g(n) = n^2 \notin \mathcal{O}(n)$
=> Widerspruch.