O-Notation, Aussagen beweisen

29.01.2012, 11:59	Kallinski	Auf diesen Beitrag antworten »
O-Notation, Aussagen beweisen Meine Frage: Hello, ich habe eine Aufgabe in der ich Aussagen über die O-Notation beweisen soll. Die Aufgabe lautet: Seien $\begin{eqnarray} f,g : \mathbb N -> \mathbb N \end{eqnarray}$ zwei Funktionen und a eine beliebige Konstante. Zeigen Sie die Korrektheit folgender Aussagen: i) $\begin{eqnarray} f\in O(f) \end{eqnarray}$ ii) $\begin{eqnarray} a\cdot O(f)\subseteq O(f) \end{eqnarray}$ iii) $\begin{eqnarray} O(f)+O(f)\subseteq O(f) \end{eqnarray}$ iv) $\begin{eqnarray} O(f)\cdot O(g) \subseteq O(fg) \end{eqnarray}$ v) $\begin{eqnarray} f\cdot O(g) \subseteq O(fg) \end{eqnarray}$ Das Problem bei dem ganzen ist, dass ich einen längeren Krankenhausaufenthalt hatte und somit ziemlich viel verpasst habe. Zusätzlich ist dies der letze Aufgabenzettel für das Modul und wenn ich den nicht mit voller Punktzahl abgebe habe ich das Modul nicht bestanden. Also ich will jetzt auch nicht,dass jemand einfach die Lösung hinschreibt und fertig, sondern ich würde mich freuen, wenn sich jemand mir annehmen könnte. Vielen Dank schonmal! Meine Ideen: Also ich habe bereits folgendes: Sei c=O(1) iii) O(f) + O(f) = c1 * f + c2 * f = (c1 + c2) * f = c * f = O(f) iv) O(f) * O(g) = c1 * f * c2 * g = (c1 * c2) * f * g = c * (f * g)= O(f * g) v) f * O(g) = f * c * g = c * (f * g) = O(f * g) Aber ob das so richtig ist? Zu i) und ii) habe ich leider keine Idee
31.01.2012, 11:50	EinGast	Auf diesen Beitrag antworten »
RE: O-Notation, Aussagen beweisen Hallo, habt ihr das so definiert: $\begin{eqnarray} \mathcal{O}(f)=\{h\colon \mathbb{N} \to\mathbb{N}\mid \exists c>0: h(n)\le c\cdot f(n) \,\,\forall n\in\mathbb{N}\} \end{eqnarray}$ Für iii) z.B. geht man so vor: Seien $\begin{eqnarray} h_1,h_2\in\mathcal{O}(f) \end{eqnarray}$ . Dann gibt es Konstanten $\begin{eqnarray} c_1,c_2>0 \end{eqnarray}$ mit $\begin{eqnarray} h_1(n)\le c_1f(n) \end{eqnarray}$ und $\begin{eqnarray} h_2(n)\le c_2f(n) \end{eqnarray}$ für alle $\begin{eqnarray} n\in\mathbb{N} \end{eqnarray}$ . Daraus folgt $\begin{eqnarray} (h_1+h_2)(n)=h_1(n)+h_2(n)\le c_1f(n)+c_2f(n)=(c_1+c_2)f(n) \end{eqnarray}$ (für alle $\begin{eqnarray} n\in\mathbb{N} \end{eqnarray}$ ) und somit $\begin{eqnarray} h_1+h_2\in\mathcal{O}(f) \end{eqnarray}$ Die übrigen Behauptungen ergeben sich nach demselben Schema.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »