0 Daumen
3,8k Aufrufe

Servus,

Hier ist meine Aufgabe , hoffentlich könnt ihr mir helfen um sie zu verstehen;

Definition:

Durch das O-Kalkül wird die Menge von Funktionen beschrieben welche höchstens
so schnell wachsen wie eine gegebene Vergleichsfunktion. Die Menge der
von (groß) O beschriebenen Funktionen wird definiert durch:

      O(g) := {ƒ | ∃c∃n0 : 0≤ |ƒ(n)| ≤ c* |g(n)| ∀n > n0 }

 

Dabei gilt:

 

    g(n) = g,  ℝ := Vergleichsfunktion

    f(n) = ƒ , ℝ := untersuchte Funktion

    c>0 := konstanter Faktor

    n0 ℕ := Schranke

Zeige oder widerlege folgende Behauptungen. Es ist kein formeller Beweis
nötig.

 

a) Sei f(n) = 2n und g(n) = n, so ist f ∈ O(g).

b) Sei f(n) = n3 und g(n) =n 2 , so ist f ∈ O(g)

 

Eigentlich es gibt noch c,d,e,...Aber zuerst will ich verstehen wie ich die a und b  lösen kann.

Und danach kann ich den Rest machen , glaube ich

Ich bitte euch ausführliche Lösung hier zu stellen.

 

Danke im Voraus

 

Gruß Jensen.

 

 

Gefragt von

1 Antwort

+2 Daumen

a) Sei f(n) = 2n und g(n) = n, so ist f ∈ =O(g).

Es muss also gelten

|f(n)| ≤ c * |g(n)|
2n ≤ c * n
2 ≤ c

Das ist erfüllt. Damit stimmt die Aussage.

b) Sei f(n) = n^3 und g(n) =n^2 , so ist f ∈ O(g)

|f(n)| ≤ c * |g(n)|
n^3 ≤ c * n^2
n ≤ c

Das ist nicht erfüllt und damit die Aussage wiederlegt.

Beantwortet von 264 k
Hi Mathecoach,

Kannst du mir sagen , wie vergleichst z.B bei a)    2 ≤ c ?

Ich meine woher weist du , dass 2 kleiner als c ist ?

Gruß Jensen!
@Jensen: Du musst 2 ≤ c umgekehrt lesen.  Für jedes c ≥ 2 ist die Bedingung in der Definition von O(g) erfüllt. z.B. für c=2. Deshalb ist a ok.

bei b)  c ≥ n findest du kein c, für das diese Bedingung immer erfüllt sein wird, weil n beliebig wachsen kann. Deshalb Antwort bei b) : nein.
Danke is es schon klar !

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
0 Daumen
1 Antwort
Gefragt 12 Jun 2014 von Gast

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...