O-Notation

01.05.2008, 18:47

H-Man

O-Notation

Sehe ich das richtig, dass beide Funktionen falsch sind?

Der linke Teil darf doch nie schneller wachsen oder größer sein, wie der rechte?

01.05.2008, 19:00

Auf diesen Beitrag antworten »

RE: O-Notation

Zitat:

Original von H-Man
Sehe ich das richtig, dass beide Funktionen falsch sind?

Du meinst beide Aussagen (nicht Funktionen) ?

a) ist falsch, aber b) ist richtig! Schau dir die Definition von $\begin{eqnarray*} O(\ldots) \end{eqnarray*}$ genau an.

01.05.2008, 19:03

H-Man

Auf diesen Beitrag antworten »

Ja, den Verdacht habe ich auch gerade gehabt...!

Man muss den recht Teil (O(...)) mit einer Konstante multiplizieren, wenn ich das richtig verstehe?

01.05.2008, 19:06

Auf diesen Beitrag antworten »

Möglicherweise meinst du damit das Richtige, aber so schlampig formuliert gibt's keine Bestätigung von mir. Augenzwinkern

01.05.2008, 19:09

H-Man

Auf diesen Beitrag antworten »

Ich wähle zum Beispiel: c=5

$\begin{eqnarray*} 5 * 2^{n} \end{eqnarray*}$

... der linke Teil wird immer größer bleiben, wie der rechte Teil!?

Nur wie "beweise" ich das am besten?

01.05.2008, 19:19

Auf diesen Beitrag antworten »

Welcher linke Teil, welcher rechte Teil, wieso "größer"? ... Meine Güte, deutlich und klar sagen:

Es ist $\begin{eqnarray*} | 2^{n+2} | \leq 5\cdot 2^n \end{eqnarray*}$ für alle $\begin{eqnarray*} n \end{eqnarray*}$ , also ist gemäß O-Definition die Aussage $\begin{eqnarray*} 2^{n+2} \in O(2^n) \end{eqnarray*}$ .

01.05.2008, 19:20

H-Man

Auf diesen Beitrag antworten »

Ist denn folgendes möglich?:

2.3b)

$\begin{eqnarray*} 2^{n+2} \end{eqnarray*}$
$\begin{eqnarray*} = 2^{n} * 2^{2} \end{eqnarray*}$
$\begin{eqnarray*} = 2^{n} * 4 \end{eqnarray*}$

Wenn ich also als Konstante 4 (oder mehr) angebe, dann wird der rechte Bereich niemals kleiner, wie der linke, da ja dann die Multiplikation immer größer ist oder gleich (bei 4)!?

01.05.2008, 19:23

H-Man

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Welcher linke Teil, welcher rechte Teil, wieso "größer"? ... Meine Güte, deutlich und klar sagen:

Es ist $\begin{eqnarray*} | 2^{n+2} | \leq 5\cdot 2^n \end{eqnarray*}$ für alle $\begin{eqnarray*} n \end{eqnarray*}$ , also ist gemäß O-Definition die Aussage $\begin{eqnarray*} 2^{n+2} \in O(2^n) \end{eqnarray*}$ .

Genau, dann habe ich das rchtig verstanden, ich wollte das mit meiner Aufteilung oben "beweisen".

Ist das so möglich zu "beweisen"?

01.05.2008, 20:41

WebFritzi

Auf diesen Beitrag antworten »

Drück dich endlich ordentlich aus. Dann kann man dir auch antworten.

01.05.2008, 20:44

H-Man

Auf diesen Beitrag antworten »

Sorry...

Ich habe meine Antwort auf die Frage nun so formuliert...

Ich hoffe das ist verständlich, vielleicht habt ihr noch Hinweise!?

01.05.2008, 21:15

WebFritzi

Auf diesen Beitrag antworten »

Du weißt schon, dass es die Technik "Beweis per Beispiel" nicht gibt?

01.05.2008, 21:16

H-Man

Auf diesen Beitrag antworten »

Aber wie kann ich das sonst machen?
Ich verstehe ja, warum es so ist, weiß aber nicht, wie ich das anders schreiben kann.

01.05.2008, 21:21

WebFritzi

Auf diesen Beitrag antworten »

Machen wir doch mal die (b). Du sollst da zeigen:

Es gibt eine Konstante c > 0 und eine nat. Zahl n0, so dass

$\begin{eqnarray*} 2^{n+2}\le c2^n \end{eqnarray*}$ für alle $\begin{eqnarray*} n\ge n_0 \end{eqnarray*}$ gilt.

Das kann ja nicht so schwer sein. Was kannst du als c und was als n0 wählen?

01.05.2008, 21:59

H-Man

Auf diesen Beitrag antworten »

c=5
n0=1

Hätte ich jetzt gewählt.

01.05.2008, 22:18

WebFritzi

Auf diesen Beitrag antworten »

OK. Das ist richtig. Aber du hast es nicht ordentlich aufgeschrieben. Mach es so:

$\begin{eqnarray*} 2^{n+2} = 2^n\cdot 2^2 = 4\cdot 2^n. \end{eqnarray*}$

Das reicht so. Du kannst dann noch drunterschreiben: "Mit n0 = 1 und c = 4 gilt also $\begin{eqnarray*} 2^{n+1}\le c2^n \end{eqnarray*}$ für alle $\begin{eqnarray*} n\ge n_0. \end{eqnarray*}$ Das beweist die Aussage."

01.05.2008, 22:23

H-Man

Auf diesen Beitrag antworten »

OK, super, danke, werde das nochmal bearbeiten.

Neue Frage »

Antworten »

O-Notation

Verwandte Themen