0 Daumen
49 Aufrufe

Frage:

Für welche der folgenden Paare von Funktionen f und g gilt f ∈ O(g)?
(a) f(n) = 3n^3 + 200, g(n) = 1/2 * (n^3) − 10

(b) f(n) = √n − 6, g(n) = 20 4^√n + 36

(c) f(n) = 2n^2 − 8n + 2, g(n) = n^3 − 17n^2 − 23451


Hallo zusammen, Ich habe diese Aufgabe aus Java. Könnte jemand mir helfen bitte?

Vielen Dank im Voraus! :)

von

1 Antwort

0 Daumen
 
Beste Antwort

Hallo,

die Definition der O-Notation lautet ja in etwa so:

Es sei \(g: \mathbb{N}\rightarrow \mathbb{R}\). Dann ist
$$ \mathcal{O}(g):=\{f:\mathbb{N}\rightarrow \mathbb{R}:\exists \alpha>0 \ \exists n \in \mathbb{N} \ \forall n\geq n_0:0\leq f(n) \leq \alpha \cdot g(n)  \} $$
die Menge aller Funktion f, die bis auf eine Konstante \(\alpha>0\) höchstens so schnell wächst wie g.

Zu (a). Du musst also ein \(\alpha>0 \) und ein \(n_0\in \mathbb{N}\) so angeben, sodass nachweislich für alle \(n\geq n_0\) diese Abschätzung gilt: \(0\leq f(n) \leq \alpha \cdot g(n)\), konkreter hier: \(0\leq 3n^3+200 \leq \alpha \cdot \left( \frac{1}{2}n^3-10 \right)\).

Um jetzt an diese beiden Werte ranzukommen, kannst du das (gerade bei Polynomen) schön sukzessive nach unten abschätzen. Dabei kann man sich den Leitkoeffizienten des Polynoms anschauen und würde hier schonmal sehen, dass \(\alpha=7>0\) ein geeigneter Kandidat sein könnte. Also kann man jetzt mal probieren:

\(\alpha\cdot g(n)=7\cdot g(n)=7\cdot \left(\frac{1}{2}n^3-10\right)\\=\frac{7}{2}n^3-70\\=\frac{6}{2}n^3+\frac{1}{2}n^3-70\\=3n^3+\frac{1}{2}n^3-70\\=3n^3+200+\left(\frac{1}{2}n^3-270\right )\\\stackrel{n\geq 10}{\geq} 3n^3+200+230\geq 3n^3+200\geq 0\).

Die Wahl \(n=10\) kann man dadurch rechtfertigen, dass die Ungleichung

\(\frac{1}{2}n^3-270\geq 230\) für alle \(n\in \mathbb{N}_{\geq 10}\) erfüllt ist.

Insgesamt gilt also mit \(\alpha=3\) und für alle \(n\geq 8=:n_0\) die Ungleichung

\(0\leq 3n^3+200 \leq \alpha \cdot \left( \frac{1}{2}n^3-10 \right)\).

Zu (b) Hier gilt doch schonmal \(\sqrt{n}\leq 4^{\sqrt{n}}\). Wenn du davon noch nicht überzeugt bist, beweise es. Versuche dann damit weiterzuarbeiten.

Zu (c). Kannst du analog wie (a) durchführen.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community