Asymptotische Komplexität

05.05.2010, 21:37

MissParker

Asymptotische Komplexität

Hallo zusammen!

Ich brauche dringend Hilfe. Ich sitze seit Stunden an einer Aufgabe und ich habe fast noch nichts auf dem Blatt stehen. Die Aufgabe:

Bweisen Sie folgenden Zusammenhang:
f(n) = O(g(n)) $\begin{eqnarray*} \Leftarrow\Rightarrow \end{eqnarray*}$ g(n) = Omega(f(n))

Omega(f(n)) enthält alle Funktionen g für die es eine Konstante c und eine Zahl $\begin{eqnarray*} n_{0} \end{eqnarray*}$ gibt, so dass für alle n $\begin{eqnarray*} \geq n_{0} \end{eqnarray*}$ gilt: g(n) ist größer oder gleich c*f(n).

O(g(n)) : Die Funktion f(n) ist in der Menge O(g(n)) , wenn es ein c>0 und ein $\begin{eqnarray*} n_{0} \end{eqnarray*}$ Element der natürlichen Zahlen gibt, so dass für alle n $\begin{eqnarray*} \geq n_{0} \end{eqnarray*}$ gilt: f(n) ist kleiner oder gleich c*g(n).

Das Umgesetzt bedeutet:

f(n) $\begin{eqnarray*} \leq \end{eqnarray*}$ c*g(n) $\begin{eqnarray*} \Leftarrow\Rightarrow \end{eqnarray*}$ g(n) $\begin{eqnarray*} \geq \end{eqnarray*}$ c*f(n)

Kann mir jemand ein Tipp geben, wie ich jetzt weiter vorgehen muss?

Ich bedanke mich schon mal im voraus für die Hilfe!

05.05.2010, 23:44

Abakus

Auf diesen Beitrag antworten »

RE: Asymptotische Komplexität

Zitat:

Original von MissParker
Das Umgesetzt bedeutet:

f(n) $\begin{eqnarray*} \leq \end{eqnarray*}$ c*g(n) $\begin{eqnarray*} \Leftarrow\Rightarrow \end{eqnarray*}$ g(n) $\begin{eqnarray*} \geq \end{eqnarray*}$ c*f(n

Hallo!

Du musst dich fragen, welche Quantoren da stehen, denn nur die Gleichungen als solche sind sicher nicht äquivalent.

Grüße Abakus smile

Neue Frage »

Antworten »

Asymptotische Komplexität

Verwandte Themen