Rechnen mit der O-Notation

04.05.2011, 09:53

Rose_xx

Rechnen mit der O-Notation

Hey zusammen!
Ich hab ein paar Aufgaben im Kurs AlgoDat zum Rechnen mit der O-Notation erhalten. Ich hab bereits das Forum hier nach ähnlichen Threads durchsucht bzw. stundenlang nach der Notation gegoogelt, aber ich checks einfach nicht unglücklich

Die Formeln $\begin{eqnarray*} f(n) \leq c \cdot g(n) \end{eqnarray*}$ und
dass der Grenzwert $\begin{eqnarray*} \lim_{n \to \infty } \frac{f(n)}{g(n)} \end{eqnarray*}$
existieren muss, ist mir bekannt.

Jetzt soll ich beispielsweise als erstes zeigen oder widerlegen:
$\begin{eqnarray*} 3n² + 30n + 300 = O(n²) \end{eqnarray*}$

ich weiß dass ichs zu
$\begin{eqnarray*} n² \cdot ( 3 + \frac{30}{n} + \frac{300}{n²} ) \end{eqnarray*}$
umschreiben kann, bzw. die 3 auch noch vorziehe.

aber wie gehe ich allgemein nun weiter vor?
kann ich die oben genannte Formel benutzen und wenn ja, was genau ist dann eigentlich g(n) bei der Aufgabe?

ich hatte auch einen Ansatz mit

3n² + 30n + 300 = c * n² (n² wegen O(n²))
c = 3
3n² + 30n + 300 = 3n²
30n + 300 = 1
30n = -299

aber das sieht nicht so ganz korrekt aus Big Laugh

Ich würde mich über jede Starthilfe, wie man sowas nu berechnet, ganz arg freuen smile

Rose

04.05.2011, 10:44

René Gruber

Auf diesen Beitrag antworten »

Bei dir ist $\begin{eqnarray*} f(n) = 3n^2 + 30n + 300 \end{eqnarray*}$ sowie $\begin{eqnarray*} g(n) = n^2 \end{eqnarray*}$ . Nun geht es um das Verhalten des Quotienten $\begin{eqnarray*} \frac{f(n)}{g(n)} \end{eqnarray*}$ für $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ . Du hast ja quasi schon berechnet

$\begin{eqnarray*} \frac{f(n)}{g(n)} = 3 + \frac{30}{n} + \frac{300}{n^2} \end{eqnarray*}$ .

Offenbar existiert da der Grenzwert für $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ (und ist gleich 3), was hinreichend (!) ist für $\begin{eqnarray*} f(n)\in O(g(n)) \end{eqnarray*}$ .

Die Existenz dieses Grenzwertes ist aber keineswegs notwendig, es wird lediglich gefordert, dass der Quotient $\begin{eqnarray*} \frac{f(n)}{g(n)} \end{eqnarray*}$ beschränkt bleibt. Insofern ist diese deine Aussage

Zitat:

Original von Rose_xx
dass der Grenzwert $\begin{eqnarray*} \lim_{n \to \infty } \frac{f(n)}{g(n)} \end{eqnarray*}$
existieren muss, ist mir bekannt.

falsch - Gegenbeispiel $\begin{eqnarray*} n\sin(n) \in O(n) \end{eqnarray*}$ , da existiert dieser Grenzwert nicht.

04.05.2011, 11:00

Rose_xx

Auf diesen Beitrag antworten »

Ah okay, dann ist das was in den Klammern von O() steht, immer g bzw. g(n) ?
das erklärt ja schonmal einiges Big Laugh

Um mal eben kurz mein Skript zu zitieren:
"Man betrachte den Grenzwert: " [wie oben geschrieben] ". Existiert dieser (d.h. er ist < unendlich), so ist f = O(g)."
daher hab ich das geschrieben mit der Existenz smile

aber das mit dem sinus war ein gutes Beispiel, danke smile

also mein Grenzwert ist da ja 3, und von daher kann ich schreiben, dass die Angabe korrekt war und f(n) element von O(n²). Muss ich "element von" schreiben oder kann ich auch ein "istgleich" benutzen?

04.05.2011, 11:23

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Rose_xx
"Man betrachte den Grenzwert: " [wie oben geschrieben] ". Existiert dieser (d.h. er ist < unendlich), so ist f = O(g)."

Das ist ja auch richtig - aber wie gesagt, als hinreichendes Kriterium.

04.05.2011, 18:09

Rose_xx

Auf diesen Beitrag antworten »

ah okay, thx!

ich hatte noch die aufgaben mit
a) 4^n = O(3^n)
b) sin² n = O(1)

ich schätzte sie beide als falsch ein, wenn mich meine Grenzwertkenntnisse nicht im Stich lassen.
$\begin{eqnarray*} \frac{4^{n}}{3^{n}} \end{eqnarray*}$ divergiert gegen unendlich(, da 4^n schneller als 3^n wächst) -> kein eindeutiger Grenzwert

und sin² n = sin (n) ² (?) und pendelt zwischen 0 und 1.

sind aber eher Vermutungen, sicher bin ich mir leider nicht.

04.05.2011, 19:44

Huy

Auf diesen Beitrag antworten »

Bei a) hast du recht, bei b) allerdings nicht, wofür du aber nichts kannst. Man muss nicht $\begin{eqnarray*} \lim_{x \to \infty} \frac{f(x)}{g(x)} < \infty \end{eqnarray*}$ überprüfen, sondern
$\begin{eqnarray*} \limsup_{x \to \infty} \left| \frac{f(x)}{g(x)} \right| < \infty \end{eqnarray*}$ .

MfG

04.05.2011, 19:52

Rose_xx

Auf diesen Beitrag antworten »

ah ja, bin ich mittlerweile auch drauf gekommen (:
meine Begründung lautet .. äähm.. hier:

Der Graph von sin²n pendelt zwischen 0 und 1. Somit gibt es keinen eindeutigen Grenzwert, jedoch liegt eine Beschränktheit vor. Die Aussage stimmt.

Weil, ich weiß ja jetzt, eindeutig existierender Grenzwert ist "nur" hinreichend, wichtig ist die Beschränktheit (:

Neue Frage »

Antworten »

Rechnen mit der O-Notation

Verwandte Themen