FANDOM


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.