O Notation

04.01.2016, 15:46

mrkrispi94

O Notation

Hallo ich muss diese Aufgabe als Hausaufgabe erledigen, kann mir da vlt einer bei helfen?

Folgende Frage :

Suche dir die folgenden Funktionen jeweils geeignete Konstanten (c1, c2 ) sowie n0 und zeige mit Hilfe dieser Konstanten, dass die jeweilige Funktion in der angegebenen Klasse liegt:
f1(n) = n−3√n ∈ ©(n)
f2(n) = n2+nlog2n ©(n2 )
f3(n) = log2(n3) ∈ ˜(log3 n)
f4(n) = 3n3+6n2 ∈ O(n3)
f5(n) = 1+5 ∈ O(1)
Für eure Hilfe wäre ich euch super dankbar!

Danke schon einmal im voraus großes Grinsen

04.01.2016, 15:50

Auf diesen Beitrag antworten »

eulerscheZahl

Das Encoding passt nicht. Versuche es am besten mit $[latex]\hbox{\LaTeX}[/latex]$ .

05.01.2016, 11:45

Auf diesen Beitrag antworten »

bola

Moin,

gerade den Thread gefunden. Ich habe die selbe Aufgabe (vermutlich auch selbe Veranstaltung). Die Aufgabe sieht folgendermaßen aus und ein Lösungsweg würde mich auch interessieren. Auch, wie ich mir diese Rechnung im Alltag vorstellen kann, z.B. mit den Konstanten.

Bei b) bin ich völlig überfragt und komme gar nicht zurecht. Ich habe es mal bis zur dritten Zeile versucht, ob das richtig ist, weiß ich leider nicht:

1. O(1), O(n), O(n^2)
2. alle Omega und Theta
3. alle Omega und Theta und O(n^2)

Aber seht selbst

05.01.2016, 12:23

Auf diesen Beitrag antworten »

eulerscheZahl

$[latex]f_1(n) = n-3\sqrt{n} = \Omega(n) \Leftrightarrow n = \mathcal{O}(n-3\sqrt{n})[/latex]$
$[latex]n = \mathcal{O}(n-3\sqrt{n}) \Leftrightarrow n \leq c\cdot (n-3\sqrt{n})[/latex]$
Es muss in n0 und c gefunden werden, sodass das für alle n >= n0 gilt.
Erweitern wir die Abschätzung:
$[latex]n-3\sqrt{n} \leq n[/latex]$ für n >= 0.

n0=1 und c=1 erfüllt die Bedingung.

$[latex]f_2(n) = n^2+n\log_2n = \Omega(n^2) \Leftrightarrow n^2 = \mathcal{O}(n^2+n\log_2n)[/latex]$
$[latex]n^2 = \mathcal{O}(n^2+n\log_2n) \Leftrightarrow n^2 \leq c(n^2+n\log_2n)\underbrace{\leq}_{n\geq 0}c(n^2+n^2)=c\cdot2n^2[/latex]$
und wieder erfüllt n0=1 und c=1 die Bedingung.

Bei $[latex]\Theta[/latex]$ musst du die Ungleichung für beide Richtungen zeigen.

bei $[latex]\frac{1.67n^2}{n}[/latex]$ bleibt effektiv ein n im Zähler. Daher $[latex]\mathcal{O}(n) und \mathcal{O}(n^2)[/latex]$ , da n eine obere Schranke gibt. Wenn es in $[latex]\mathcal{O}(n)[/latex]$ ist, dann auch in $[latex]\mathcal{O}(n)[/latex]$ , da n < n^2.
Gleichzeitig ist es in $[latex]\Omega(1)[/latex]$ und $[latex]\Omega(n)[/latex]$ (obere Schranke).
Wenn du $[latex]\mathcal{O}[/latex]$ und $[latex]\Omega[/latex]$ ankreuzt, kannst du $[latex]\Theta[/latex]$ auch gleich nehmen, per Definition.

$[latex]3^{2log_3(n)} = n^2[/latex]$ macht einiges leichter.

05.01.2016, 14:16

Auf diesen Beitrag antworten »

bola

Danke für deine Antwort.

Ich bin bei a) nach folgender Definition gegangen:
$[latex]\Omega(g(n)) = \{f(n) | (\exists c_1,c_2,n_0 > 0), (\forall_n \ge n_0): 0 \le c_1 g(n) \le f(n)\}[/latex]$

und dachte mir, dass ich für g(n) das n aus $[latex]\Omega(n)[/latex]$ nehmen muss.
Für f(n) dann $[latex] n - 3\sqrt n [/latex]$

Dann hätte ich diese Ungleichung:

$[latex] 0 \le c * n \le n - 3\sqrt n [/latex]$

Als Konstanten habe ich für c = 1 und für n = 0.
Dann ginge das Ganze auf.
Bei n=1 würde das bei mir nicht mehr funktionieren, weil $[latex] 1 - 3 * \sqrt 1 = -2 [/latex]$

Aber anscheinend mache ich es mir wohl zu einfach unglücklich

05.01.2016, 14:23

Auf diesen Beitrag antworten »

eulerscheZahl

Kannst du bitte ich in der ersten Formel die Klammern richten? Es geht eine mehr auf als zu.

05.01.2016, 14:36

Auf diesen Beitrag antworten »

bola

Wurde geändert inkl. geschweifter Klammern

05.01.2016, 14:55

Auf diesen Beitrag antworten »

eulerscheZahl

Nehmen wir deine Definition:
$[latex]\Omega(\underbrace{n}_{g(n)}) = \underbrace{n-3\sqrt{n}}_{f(n)}[/latex]$
$[latex]0\leq c n \leq n-3\sqrt n[/latex]$
c=1 ist falsch gewählt, also versuchen wir was zwischen 0 und 1. z.B: 0.5
$[latex]\frac{1}{2}n \leq n-3\sqrt n[/latex]$ , für n=36 gilt Gleichheit, darüber hinaus ist die Ungleichung immer erfüllt.

05.01.2016, 15:00

Auf diesen Beitrag antworten »

Karlito

Du kannst es so machen. Aber n muss nicht durch n0 ersetzt werden. Es muss nur gelten, dass $[latex]c\cdot g(n)\le f(n)[/latex]$ für alle $[latex]n \ge n_0[/latex]$ gilt. [latex]n_0[/latex]

ist dabei auch abhängig davon, wie c gewählt ist.

Du kannst dazu weiter umformen, damit es leichter sichtbar ist:
$[latex] c * n & \le & n - 3\sqrt n ~|~ :n c & \le & 1 - 3\frac{\sqrt n}{n} c -1 & \le & 1 - 3\frac{\sqrt n}{n} \frac{c -1}{3} & \le & \frac{\sqrt n}{n} [/latex]$

Wählt man jetzt c = 4, so sieht man, dass für n0 = 1 die Ungleichung immer erfüllt ist, da n schneller wächst als $[latex]\sqrt n[/latex]$ .

Gruß,

Karlito

05.01.2016, 15:01

Auf diesen Beitrag antworten »

bola

Zitat:

Original von eulerscheZahl
Nehmen wir deine Definition:
$[latex]\Omega(\underbrace{n}_{g(n)}) = \underbrace{n-3\sqrt{n}}_{f(n)}[/latex]$
$[latex]0\leq c n \leq n-3\sqrt n[/latex]$
c=1 ist falsch gewählt, also versuchen wir was zwischen 0 und 1. z.B: 0.5
$[latex]\frac{1}{2}n \leq n-3\sqrt n[/latex]$ , für n=36 gilt Gleichheit, darüber hinaus ist die Ungleichung immer erfüllt.

Das ist der Punkt den ich nicht verstehe.
Kann man nicht einfach $[latex]0 \le 0 \le 0 [/latex]$ raus bekommen?

Und gibt es eine "Regel", wie man c und n, bzw. bei Theta dann auch c2 bestimmt? Oder funktioniert das nur mit Probieren?

Zitat:

Original von Karlito
Du kannst es so machen. Aber n muss nicht durch n0 ersetzt werden. Es muss nur gelten, dass $[latex]c\cdot g(n)\le f(n)[/latex]$ für alle $[latex]n \ge n_0[/latex]$ gilt. [latex]n_0[/latex]

Sieht gut aus. Vielen Dank. Werde ich so mal ausprobieren

05.01.2016, 15:08

Auf diesen Beitrag antworten »

eulerscheZahl

@Karlito
Was ist denn aus dem Minus vor der 3 geworden?

$[latex]4\cdot 1 \leq 1-3\sqrt n[/latex]$ gilt nicht (c und n0 in die Ungleichung vom Anfang eingesetzt).

05.01.2016, 15:14

Auf diesen Beitrag antworten »

Karlito

Zitat:

Original von bola
Das ist der Punkt den ich nicht verstehe.
Kann man nicht einfach $[latex]0 \le 0 \le 0 [/latex]$ raus bekommen?

Nope! Nur wenn f(n) = 0, da f(n) ja sonst für irgendein n oder konstant ungleich 0 ist.

Zitat:

Original von bola
Und gibt es eine "Regel", wie man c und n, bzw. bei Theta dann auch c2 bestimmt? Oder funktioniert das nur mit Probieren?

Scharfes Hinsehen Augenzwinkern

Und Erfahrung. Wenn man die Ungleichungen günstig umformt sieht man es eigentlich immer, wie man c und n0 wählen muss.

Zitat:

Original von bola
@Karlito
Was ist denn aus dem Minus vor der 3 geworden?

Ups, Vorzeichen vergessen. War 'ne Prüfung, hast du gut bemerkt Augenzwinkern

Ich hoffe ich habe nicht noch mehr (Schussel)fehler gemacht.

Gruß,

Karlito

05.01.2016, 15:29

Auf diesen Beitrag antworten »

eulerscheZahl

Vielleicht tust du dir mit einer bildlichen Erklärung leichter:
Du siehst 1/2*n (rot) und n-3*sqrt(n) (blau).
Ziel ist es, ein n0 zu finden, sodass ab dann immer die blaue Kurve oberhalb der roten liegt. Das ist am n=36 der Fall.

06.01.2016, 00:31

Auf diesen Beitrag antworten »

bola

Bzgl. $[latex]0 \le 0 \le 0[/latex]$ schließt sich ja schon durch die Definition aus, wie ich gerade erst erkannt habe.
Ansonsten setze ich mich jetzt dran und hoffe, dank eurer Hilfe voran zu kommen.

Vielen Dank nochmal

Neue Frage »

Antworten »

O Notation

Verwandte Themen