Informatiker Board | Druckvorschau: O Notation

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- O Notation (http://www.informatikerboard.de/board/thread.php?threadid=2722)

Geschrieben von mrkrispi94 am 04.01.2016 um 15:46:

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

Geschrieben von eulerscheZahl am 04.01.2016 um 15:50:

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

Geschrieben von bola am 05.01.2016 um 11:45:

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

Geschrieben von eulerscheZahl am 05.01.2016 um 12:23:

$[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.

Geschrieben von bola am 05.01.2016 um 14:16:

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

Geschrieben von eulerscheZahl am 05.01.2016 um 14:23:

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

Geschrieben von bola am 05.01.2016 um 14:36:

Wurde geändert inkl. geschweifter Klammern

Geschrieben von eulerscheZahl am 05.01.2016 um 14:55:

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.

Geschrieben von Karlito am 05.01.2016 um 15:00:

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

Geschrieben von bola am 05.01.2016 um 15:01:

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

Geschrieben von eulerscheZahl am 05.01.2016 um 15:08:

@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).

Geschrieben von Karlito am 05.01.2016 um 15:14:

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

Geschrieben von eulerscheZahl am 05.01.2016 um 15:29:

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.