Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » O-Notation Beweis ohne Grenzwertbetrachtung

O-Notation Beweis ohne Grenzwertbetrachtung

Universität / Fachhochschule

Sonstiges

Tags: Beweis, O-Notation, ohne Limes

InfoStudi aktiv_icon

15:08 Uhr, 11.09.2016

Hallo zusammen,

die Definition zur O-Notation lautet nach meiner Vorlesung wie folgt:

O (f (n)) = {g (n) :

Es existiert ein

c > 0, n_{0} > 0,

so dass für alle

n \geq n_{0}

gilt

g (n) \leq c \cdot f (n)}

Die Betrachtung über Limes dürfen wir dabei nicht verwenden. Ich habe mir ein paar "leichtere" Beispiele dazu angesehen. Eines davon lautet wie folgt:
Behauptung:

10 \cdot n^{2} + 4 \cdot n + 2 = O (n^{2})

In dem Beispiel wurde wie folgt vorgegangen

10 \cdot n^{2} + 4 \cdot n + 2 \leq c \cdot n^{2}

(soweit klar, da die Funktionen einfach in den Teil

g (n) \leq c \cdot f (n)

eingesetzt worden sind)
nun wurde

c = 11

angenommen (mir ist nicht ganz klar, ob man

n_{0}

oder

c

als erstes wählt und wenn man es wählt, wie man die "richtige" Wahl hierbei erkennen kann)

\Leftrightarrow 10 \cdot n^{2} + 4 \cdot n + 2 \leq 11 \cdot n^{2} | - 10 \cdot n^{2}

\Leftrightarrow 4 \cdot n + 2 \leq n^{2}

(nun wurde

n_{0} \geq 5

gewählt)
Mit

c = 11

und

n_{0} \geq 5

Ich habe für mich noch nicht erkennen können wann man ein festes

c =

einem Wert wählt und wann

c \geq

einem Wert sein soll. Gibt es dabei eine Besonderheit die man bei der jeweiligen Aufgabe dieser Art zu beachten hat?

n_{0}

soll ja der erste Index sein ab dem die Formel

g (n) \leq c \cdot f (n)

gilt.

Ich habe obige Beispielaufgabe mit einem anderen Ansatz noch einmal probiert, er lautet wie folgt:

10 \cdot n^{2} + 4 \cdot n + 2 \leq c \cdot n^{2} | : n^{2}

\Leftrightarrow 10 + \frac{4}{n} + \frac{2}{n^{2}} \leq c

Wähle

n_{0} = 1

|muss ich hier

n_{0} \geq 1

schreiben?

\Leftrightarrow 10 + 4 + 2 = 16 \leq c

die Formel ist erfüllt für

c \geq 16

und

n_{0} = 1

Wäre meine Vorgehensweise trotz anderer Werte trotzdem korrekt? Gibt es eine Eindeutigkeit bei den Ergebnissen oder gibt es mehr als eine "richtige" Lösung solch einer Aufgabe?

Grüße und vielen Dank,

InfoStudi

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Zu diesem Thema passende Musteraufgaben einblenden

Apilex aktiv_icon

17:54 Uhr, 11.09.2016

An sich ist es egal ob du

c

oder

n_{0}

zuerst wählst und

n_{0}

muss auch nicht der erste Index sein ab dem die Bedingung gilt sondern nur irgendeiner sodas es

\forall n \geq n_{0}

aufjedenfall auch gilt.

üblicherweise wird versucht das problem möglichst allgmein zu lösen. Deshalb ermitelt mann entweder einen festen Startwert

n_{0}

und berechnet dann die Möglichen

c

so das die Bedingung erfüllt ist ,wobei diese

c

sich zusammenfassen lassen zu

c \geq

Zahl oder mann wählt ein festes

c

und gibt dann alle möglichen Startwerte

n_{0}

an in dem man den kleinstmöglichen berechnet und dann gilt alle

n_{0} \geq

(kleinst möglicher

n_{0})

Falls man

n_{0}

zuerst festlegt mit

c \geq

"Zahl" stellt man sich die Frage wie weicht meine Funktion

f (n)

ab einem bestimmten

n = n_{0}

maximal

g (n)

\to

nähmlich maximal

\frac{g (n_{0})}{f (n_{0})} =

"Zahl"

Falls

c

zuerst festgelegt wird geht es darum ab welchem Zeitpunkt

n_{0} : \frac{g (n)}{f (n)} \leq c

ist.

Für

O (...)

Aufgaben ist es egal was man zuerst festlegt da sowohl

c

als auch

n_{0}

sehr groß sein dürfen( solange

c \in ℝ

und

n_{0} \in ℕ)

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1322471

1322440

	Status: nicht eingeloggt	Noch nicht registriert?