O-Notation, bezogen auf Informatik

20.11.2018, 21:03

Kathreena

O-Notation, bezogen auf Informatik

Ordnen Sie folgende Komplexitätsklassen aufsteigend und kennzeichnen Sie gleichmächtige
Komplexitätsordnungen (log bezeichnet den Logarithmus zur Basis 10, ld bezeichnet den
Logarithmus zur Basis 2). Begründen Sie Ihre Antwort exemplarisch mit Hilfe der Definition
der O-Notation.

$\begin{eqnarray*} O(n \cdot log(n)) \end{eqnarray*}$
$\begin{eqnarray*} O(n^3) \end{eqnarray*}$
$\begin{eqnarray*} O(n^2+n) \end{eqnarray*}$
$\begin{eqnarray*} O(2n) \end{eqnarray*}$
$\begin{eqnarray*} O(log(n^2)) \end{eqnarray*}$
$\begin{eqnarray*} O(n^n) \end{eqnarray*}$
$\begin{eqnarray*} O(2^n) \end{eqnarray*}$
$\begin{eqnarray*} O(n^2) \end{eqnarray*}$

Meine Idee:
Ich hoffe das nich so verkehrt ist, das in dieses Forum zu posten.

Die Definition die ich habe ist:
$\begin{eqnarray*} O(f) = { g:N_0 \rightarrow N_0| \exists c>0, n_0: (\forall n \geq n_0: g(n) \leq c \cdot f(n)) } \end{eqnarray*}$

Also so wie ichs verstanden habe ist dieses groß O die obere Schranke.

Wenn ich die Klassen aufsteigend ordnen soll, wäre ich so vorgegangen, ich plotte einfach mal alle Funktionen, und schau welche am schnellsten gegen unendlich gehn, oder welche eventuell sogar nen Grenzwert haben. Dann komm ich auf:

$\begin{eqnarray*} O(log(n^2)) < O(2n) < O(n\cdot log(n)) < O(n^2) \leq O(n^2+n) < O(n^3) < O(2^n) < O(n^n) \end{eqnarray*}$

Nur wie begründe ich das nun.

20.11.2018, 22:57

HAL 9000

Auf diesen Beitrag antworten »

Die Reihung ist soweit richtig, aber: $\begin{eqnarray*} O(f(n)) \end{eqnarray*}$ ist ja eine Menge von Funktionen $\begin{eqnarray*} g \end{eqnarray*}$ , die der entsprechenden Landau-Bedingung genügen.

Im dem Sinne solltest du es besser mit dem passenden Mengenoperator schreiben:

$\begin{eqnarray*} O(\log(n^2)) \subset O(2n) \subset O(n\cdot \log(n)) \subset O(n^2) = O(n^2+n) \subset O(n^3) \subset O(2^n) \subset O(n^n) \end{eqnarray*}$

Das kann man dann so lesen: Für jede Funktion $\begin{eqnarray*} g\in O(\log(n^2)) \end{eqnarray*}$ gilt auch $\begin{eqnarray*} g\in O(2n) \end{eqnarray*}$ , usw.

Wie weist man nun diese Kette nach? Nun, hinreichend für $\begin{eqnarray*} O(f(n)) \subset O(g(n)) \end{eqnarray*}$ wäre auf jeden Fall $\begin{eqnarray*} \lim_{n\to\infty} \frac{f(n)}{g(n)} = 0 \end{eqnarray*}$ . Das kannst du hier der Reihe nach abklappern.

P.S.: Dein $\begin{eqnarray*} O(n^2) \subseteq O(n^2+n) \end{eqnarray*}$ ist zwar nicht falsch, aber unnötig unpräzise - beide Funktionsklassen sind gleich.

20.11.2018, 23:05

zweiundvierzig

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
P.S.: Dein $\begin{eqnarray*} O(n^2) \subseteq O(n^2+n) \end{eqnarray*}$ ist zwar nicht falsch, aber unnötig unpräzise - beide Funktionsklassen sind gleich.

Ebenso könnte man O(log(n^2)) = O(log(n)) und O(2n) = O(n) vereinfachen, wenn auch nicht explizit gefordert.

21.11.2018, 12:35

Kathreena

Auf diesen Beitrag antworten »

Danke, ja dachte ich mir schon. Ja muss das auf die einfachste Form bringen, auch wenns nicht in der Angabe steht.

Sollte es nun selber hinbekommen.

Neue Frage »

Antworten »

O-Notation, bezogen auf Informatik

Verwandte Themen