Oh, Omega und Theta-Kalkül

23.04.2006, 13:15	DreamTheater123	Auf diesen Beitrag antworten »
Oh, Omega und Theta-Kalkül Hi Ich habe grad Probleme bei den Oh, Omega und Theta-Kalkülen. Und zwar möchte folgende Aussagen beweisen (oder wiederlegen): 1. $\begin{eqnarray} f(n)=\Theta (g(n))\Rightarrow af(n) = \Omega (g(n)) \end{eqnarray}$ 2. $\begin{eqnarray} f(n)=O(g(n)) \Rightarrow log_2(f(n))=O(log_2(g(n))) \end{eqnarray}$ 3. $\begin{eqnarray} f(n)=O(h(n)) \And g(n)=O(h(n)) \Rightarrow h(n)=\Omega(f(n)+g(n)) \end{eqnarray}$ Hierbei sind: $\begin{eqnarray} f,g,h: \mathbb N \rightarrow \mathbb R^{>=2} \end{eqnarray*}$ Und a Konstant echt größer als 0. Meine Ansätze werde ich gleich im Anschluss posten. Gebt mir nur ein wenig Zeit. fg DreamTheater
23.04.2006, 13:45	DreamTheater123	Auf diesen Beitrag antworten »
1. $\begin{eqnarray} f(n) = \Theta(g(n)) \end{eqnarray}$ $\begin{eqnarray} \Rightarrow f(n)=\Omega(g(n)) \end{eqnarray}$ $\begin{eqnarray} a f(n) = \Omega (g(n)) \end{eqnarray}$ Fall 1: a>=1 Hier gilt immer $\begin{eqnarray} a * f(n)=\Omega(g(n)) \end{eqnarray}$ , da f(n) dadurch vergrößert wird. Somit bleibt g(n) eine untere Schranke. Fall 2: 0<a<1 Hier gibt es ein c aus R mit $\begin{eqnarray} 0\leq cg(n)\leq af(n) \end{eqnarray}$ . Wähle c:=a und es gilt $\begin{eqnarray} 0\leq cg(n)\leq af(n) \end{eqnarray}$ . ========================================== 2. Sei f(n) und g(n) jeweils Funktionen und es gelte für n gegen unendlich: $\begin{eqnarray} f(n) \leq g(n) \end{eqnarray}$ $\begin{eqnarray} \Rightarrow 2^{log_2(f(n))} \leq 2^{log_2(g(n))} \end{eqnarray}$ $\begin{eqnarray} \Rightarrow log_2(f(n)) \leq log_2(g(n)) \end{eqnarray}$ Somit gilt: $\begin{eqnarray} f(n)=O(g(n)) \Rightarrow log (f(n)) = O(log (g(n))) \end{eqnarray}$ ============================================ 3. $\begin{eqnarray} f(n) = O(h(n)) \And g(n) = O(h(n)) \end{eqnarray}$ $\begin{eqnarray} \Rightarrow h(n)=\Omega(f(n))\And h(n)=\Omega(g(n)) \end{eqnarray}$ $\begin{eqnarray} \Rightarrow h(n) = \Omega(f(n) + g(n)) \end{eqnarray}$ Beachte: Addiert man 2 Funktionen, so gilt wenn die erste Funktion das Wachstum c1 hat und die andere das Wachstum c2 mit c1<=c2 dann gilt im Falle c1=c2, dass die Summe der beiden Funktionen das Wachstum c3=c2=c1 hat. Im Falle c1<c2 gilt dann dass die Summe der beiden Funktionen das Wachstum c3=c2 hat. Somit wird das Wachstum der Summe 2er Funktionen nie das wachstum der Funktion mit dem höchsten Wachstum überschreiten. Daher gilt: $\begin{eqnarray} \Rightarrow h(n) = \Omega(f(n) + g(n)) \end{eqnarray*}$ SO, das wärn meine Ausführungen bis dahin. Was kann man da dran verbessern? Etwas besseres ist mir noch nicht eingefallen

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »