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.

Störung durch Adblocker erkannt!


Wikia ist eine gebührenfreie Seite, die sich durch Werbung finanziert. Benutzer, die Adblocker einsetzen, haben eine modifizierte Ansicht der Seite.

Wikia ist nicht verfügbar, wenn du weitere Modifikationen in dem Adblocker-Programm gemacht hast. Wenn du sie entfernst, dann wird die Seite ohne Probleme geladen.

Auch bei FANDOM

Zufälliges Wiki