Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » (O-Notation), zeigen: O(an) = O(bn)

(O-Notation), zeigen: O(an) = O(bn)

Universität / Fachhochschule

Tags: Algorithmus, Folgen, Notation

Philex aktiv_icon

16:31 Uhr, 09.02.2014

Hallo liebes Forum,

ich habe folgende Aufgabe, die mir Schwierigkeiten bereitet:

Gegeben sind die beiden Folgen

a (n) = 7 +

4n³

+

n²

b (n) =

m³

+ 2

Zeigen Sie, dass gilt:

O (a_{n}) = O (b_{n})

Ich weiß nicht, wie ich das zeigen soll. Also mir ist klar, dass ihre Laufzeit sich gleich schnell, um O(n³) steigert.
Der Weg zur Bestimmung der Steigung über die erste Ableitung kommt mir da in den Sinn, aber die Funktionen haben beide an den gleichen Stellen unterschiedliche Steigungen.

Vielleicht über den Limes / Wendepunkte? Beide Funktionen gehen gegen

- \infty

für

x < 0

und

+ \infty

für

x > 0

und besitzen nur einen Wendepunkt...

In einem anderen Forum hat man mir folgenden Tipp gegeben:

a_{n} \in O (b_{n})

und

b_{n} \in O (a_{n})

folgt

O (a_{n}) = O (b_{n})

. Benutze die Definition des Landau-Symbols!

Daraus werde ich aber überhaupt nicht schlau... Leider meldet sich da auch keiner mehr.

Insofern hoffe ich, dass ihr mir helfen könnt :-)

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

DerDepp aktiv_icon

16:41 Uhr, 10.02.2014

Hossa :-)

Die O-Notation ist in der Informatik sehr verbreitet und leider etwas irreführend. Ist

g : N \to ℜ

eine Funktion, dann bezeichnet O(g) die Menge aller Funktion

f : N \to ℜ

, für die gilt:

Es gibt ein

c > 0

, so dass für fast alle

n

gilt:

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

c

ist eine reelle positive Zahl. Der Ausdruck "für fast alle

n

" bedeutet, es gibt ein bestimmtes

n_{0}

, so dass die Aussage für alle

n \geq n_{0}

gilt. Mit anderen Worten, die Aussage gilt ab einem bestimmten

n_{0}

für alle dann folgenden natürlichen Zahlen.

In deinem konkreten Fall haben wir nun:

a (n) = 7 + 4 n^{3} + n^{2} = 4 n^{3} + n^{2} + 7 < 4 n^{3} + n^{2} + 9 \binom{\leq}{(n \geq 3)} 4 n^{3} + 2 n^{2} < 4 n^{3} + 3 n^{2} \binom{\leq}{(n \geq 3)} 4 n^{3} + n^{3} = 5 n^{3}

n \geq 3

gilt also:

a (n) = 7 + 4 n^{3} + n^{2} < 5 n^{3}

. Damit ist

a (n) \in O (n^{3})

bzw.

a (n) = O (n^{3})

, wie man in der Informatik gerne irreführend schreibt.

Weiter gilt:

b (m) = m^{3} + 2 < m^{3} + 8 \binom{\leq}{(m \geq 2)} m^{3} + m^{3} = 2 m^{3}

.

Ab

m \geq 2

gilt also:

b (n) = m^{3} + 2 < 2 m^{3}

. Damit ist

b (m) \in O (m^{3})

bzw.

b (m) = O (m^{3})

.

Beide Funktionen

a (n)

und

b (m)

sind also Element der gleichen Menge

O (n^{3})

, oder wie man salopp in der Informatik schreibt:

O (a) = O (b)

.

Ok?

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

1145214

1144999

	Status: nicht eingeloggt	Noch nicht registriert?