Additionsregel Beweisen (O-Notation)

13.02.2012, 12:19	rawfood	Auf diesen Beitrag antworten »
Additionsregel Beweisen (O-Notation) Hallo, In meinem Skript ist eine Selbsttestaufgabe. Und zwar folgende: Seien $\begin{eqnarray} T_{1}(n) \end{eqnarray}$ und $\begin{eqnarray} T_{2}(n) \end{eqnarray}$ die Laufzeiten zweier Programmstücke. P1 und P2. Sei ferner $\begin{eqnarray} T_{1}(n)=O(f(n)) \end{eqnarray}$ , $\begin{eqnarray} T_{2}(n)=O(g(n)) \end{eqnarray}$ Beweisen Sie folgende Eigenschaften der O-Notation: Addititionsregel : $\begin{eqnarray} T_{1}(n)+T_{2}(n)=O(max(f(n),g(n))) \end{eqnarray}$ und Multiplikationsregel : $\begin{eqnarray} T_{1}(n) \cdot T_{2}(n)=O(f(n) \cdot g(n))) \end{eqnarray}$ . Für die Additionsregel: $\begin{eqnarray} <br /> T_{1}(n)+T_{2}(n)<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> =O(f(n))+O(g(n))<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> =O(f(n)+g(n))<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> =O(f(n)) \oplus O(g(n))<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> =O(max(f(n),g(n))<br /> \end{eqnarray}$ Ich habe gar keine Erfahrung im Beweisen und habe einfach mal gemacht. Bitte um Hilfe. Lg Rf
16.02.2012, 20:20	Abakus	Auf diesen Beitrag antworten »
RE: Additionsregel Beweisen (O-Notation) Hallo, der erste Schritt ist, dass du dir die Definition der O-Mengen klarmachen solltest, ebenso der verwendeten Schreibweise mit dem Gleichheitszeichen. Kannst du dazu etwas sagen? Dann könntest du bei deinen Beweisen über die Definition der O-Mengen gehen letztendlich. Abakus

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »