0 Daumen
373 Aufrufe

Hallo erstmal!

Ich habe zur Zeit mit der Berechnung der asymptotischen Ordnung zu kämpfen. Eigentlich mehr ein Problem der Informatik, aber in diesem Fall sortiere ich es lieber hier ein, als in der Stacklounge, da die Fragestellung bzw. meine Probleme eher mathematischer Natur sind. Sollte dies doch ein Problem sein, bitte einen Hinweis geben, dann eröffne ich das ganze dort neu.


Aufgabe:

Beweis anhand der Definition der asymptotischen Ordnung:

$$ O(f) = {T | T: \mathbb{N}\rightarrow \mathbb{R}_{0}^{+} \; \text{und} \; \exists c \in R^{+} \exists n_{0} \in \mathbb{N} \; \forall n \geq n_{0}: T(n) \leq c*f(n)}$$

Es soll bewiesen werden für:

$$n^2+2n+3 \in O(n^2)$$

$$log(n) \in O(n)$$

$$2^{n+a} \in O(3^n)$$


Problem/Ansatz:

Nachdem ich nach langer Zeit erstmal wieder ins Rechnen kommen musste, habe ich zumindest für die erste Ungleichung eine Lösung gefunden.

$$ n^2+2n+3 \leq 2n^2$$

hat ja durch Lösen der Quadratischen Funktion die Lösung $$3 \leq n$$

So ergeben sich weitere Ungleichungen:

$$log(n) \leq c*n$$

$$2^{n+a} \leq c*3^n$$

Leider habe ich für die folgenden Teile keine guten Ansätze. Höchstens bei der letzten Teilaufgabe, das man über die Potenzgesetze gehen könnte, die Exponenten aufteilt und dann 2a als Konstante nimmt.

Avatar von

1 Antwort

0 Daumen

n2+2n+3≤2n2

Hat die Lösungsmenge {n|(3-√17)/2≤n≤(3+√17)/2}

Avatar von 123 k 🚀

n^2+2n+3≤2n^2    hat die Lösungsmenge {n|-1≤n≤3}

Aha.

Danke für die Antwort, da c aber in R+ sein soll, ist das für diese Aufgabe keine mögliche Lösung. Alternativ geht ja auch c=6 n0=1

n2+2n+3≤2n2    hat die Lösungsmenge {n|-1≤n≤3}
nach kommentarloser Korrektur:Lösungsmenge {n|(3-√17)/2≤n≤(3+√17)/2}

Die Ungleichung  n+ 2n + 3 ≤ 2n2  hat über ℝ die

 Lösungsmenge  L = ] -∞ ; -1 ] ∪ [ 3 ; ∞ [

Bezogen auf n∈ℕ [ n∈ℝ+]  also n ≥ 3 (wie im Fragetext angegeben)

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community