O-Notation

17.07.2008, 00:02

hyperbel

O-Notation

Hallo.

Ich schreibe morgen eine Analysis-Klausur und habe eine kleine Frage.

Es geht um die O-Notation.

Wir sollten gucken, ob der folgende Satz allgemeintgültig ist, und falls nein, ein Gegenbeispiel finden:

"Wenn $\begin{eqnarray*} f(n) = O (g(n)) \end{eqnarray*}$ , dann folgt daraus $\begin{eqnarray*} f(n) \cdot g(n) = O (g(n)) \end{eqnarray*}$ ."

Unsere Tutorin meinte, das sei falsch und hat ein Gegenbeispiel genannt:

" Nehmen wir $\begin{eqnarray*} f(x)=x² \end{eqnarray*}$ und $\begin{eqnarray*} g(x)=x^5 \end{eqnarray*}$ , dann kann $\begin{eqnarray*} f(x) \cdot g(x) \end{eqnarray*}$ , also $\begin{eqnarray*} x^7 \end{eqnarray*}$ nicht die O-Notation $\begin{eqnarray*} x^7 <= c \cdot x^5 \end{eqnarray*}$ erfüllen. Also ist die Aussage falsch."

Was mich stört ist folgendes: Ich habe mal beide Funktionen $\begin{eqnarray*} x^5 \end{eqnarray*}$ und $\begin{eqnarray*} x^7 \end{eqnarray*}$ geplottet und für $\begin{eqnarray*} c \end{eqnarray*}$ einen riesigen Wert eingesetzt und tatsächlich war für ein riesiges c $\begin{eqnarray*} x^5 \end{eqnarray*}$ wirklich größer als $\begin{eqnarray*} x^7 \end{eqnarray*}$ .

Und trotzdem soll die Ungleichung nicht erfüllt sein. Wie ist das zu erklären?

17.07.2008, 00:12

kiste

Auf diesen Beitrag antworten »

Für jedes c gibt es ein x mit $\begin{eqnarray*} x^7 > cx^5 \end{eqnarray*}$ .
Umformen zu $\begin{eqnarray*} x^2 > c \end{eqnarray*}$ also ist für $\begin{eqnarray*} x>\sqrt c \end{eqnarray*}$ die Ungleichung erfüllt

17.07.2008, 00:51

hyperbel

Auf diesen Beitrag antworten »

Aber ich soll ja gerade nachweisen, dass für kein c die Ungleichung erfüllt ist.
Ich hab mir gedacht, ich teile die gesamte Ungleichung durch x^2.

Dann erhalte ich x^2 <= c und das gilt ja nicht, weil x² nicht beschränkt ist.

17.07.2008, 11:56

Auf diesen Beitrag antworten »

Hi,

Zitat:

Original von hyperbel
Aber ich soll ja gerade nachweisen, dass für kein c die Ungleichung erfüllt ist.
Ich hab mir gedacht, ich teile die gesamte Ungleichung durch x^2.

Dann erhalte ich x^2 <= c und das gilt ja nicht, weil x² nicht beschränkt ist.

genau das hat kiste ja gepostet Augenzwinkern

Er hat eben gezeigt, dass für hinreichend große x gilt: x^7 > c*x^5 für alle c.

Das Problem am Plotten: Du hast nur einen sehr beschränkten Wertebereich, du musst aber alle x betrachten, d.h., auf deinem Plot müsste z.b. auch 10^100 als Wert auftauchen (und 10^100 ist wirklich klein im Vergleich mit der Unendlichkeit).

Ansonsten schau dir diese formale Defition an:
http://de.wikipedia.org/wiki/Landau-Symb...male_Definition
Und x^7/x^5 = x^2 ist ja nicht beschränkt.

17.07.2008, 15:35

WebFritzi

Auf diesen Beitrag antworten »

Man kann genauso f(x) = g(x) = x als Gegnbeispiel wählen. Verstehe nicht, wieso manchmal so ausgefallene Dinge anstatt dem Naheliegendsten genommen werden.

17.07.2008, 15:57

Tomtomtomtom

Auf diesen Beitrag antworten »

Du wärst übrigens imho wesentlich weniger verwirrt, wenn nicht so eine komische Schreibweise verwendet würde. Ich verstehe bis heute nicht, warum viele Leute f(n)=O(g(n)) schreiben statt $\begin{eqnarray*} f\in O(g) \end{eqnarray*}$ . Bei letzterem steckt schon allein in der Symbolik viel mehr Wahrheit, dazu ist es noch kürzer.

Neue Frage »

Antworten »

O-Notation

Verwandte Themen