Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Theoretische Informatik » O Notation » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen O Notation
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
mrkrispi94
Grünschnabel


Dabei seit: 04.01.2016
Beiträge: 1

O Notation Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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:46 mrkrispi94 ist offline Beiträge von mrkrispi94 suchen Nehmen Sie mrkrispi94 in Ihre Freundesliste auf
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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

__________________
Syntax Highlighting fürs Board (Link)

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von eulerscheZahl: 04.01.2016 15:50.

04.01.2016 15:50 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
bola
Grünschnabel


Dabei seit: 05.01.2016
Beiträge: 5

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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

bola hat dieses Bild (verkleinerte Version) angehängt:
Unbenannt.png

05.01.2016 11:45 bola ist offline Beiträge von bola suchen Nehmen Sie bola in Ihre Freundesliste auf
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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

__________________
Syntax Highlighting fürs Board (Link)
05.01.2016 12:23 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
bola
Grünschnabel


Dabei seit: 05.01.2016
Beiträge: 5

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von bola: 05.01.2016 14:35.

05.01.2016 14:16 bola ist offline Beiträge von bola suchen Nehmen Sie bola in Ihre Freundesliste auf
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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

__________________
Syntax Highlighting fürs Board (Link)
05.01.2016 14:23 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
bola
Grünschnabel


Dabei seit: 05.01.2016
Beiträge: 5

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Wurde geändert inkl. geschweifter Klammern
05.01.2016 14:36 bola ist offline Beiträge von bola suchen Nehmen Sie bola in Ihre Freundesliste auf
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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.

__________________
Syntax Highlighting fürs Board (Link)
05.01.2016 14:55 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
Karlito Karlito ist männlich
Kaiser


Dabei seit: 11.04.2011
Beiträge: 1.461

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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]<br />
c * n & \le & n - 3\sqrt n ~|~ :n<br />
c & \le & 1 - 3\frac{\sqrt n}{n}<br />
c -1 & \le & 1 - 3\frac{\sqrt n}{n}<br />
\frac{c -1}{3} & \le & \frac{\sqrt n}{n}<br />
[/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:00 Karlito ist offline E-Mail an Karlito senden Beiträge von Karlito suchen Nehmen Sie Karlito in Ihre Freundesliste auf
bola
Grünschnabel


Dabei seit: 05.01.2016
Beiträge: 5

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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] ist dabei auch abhängig davon, wie c gewählt ist.

Du kannst dazu weiter umformen, damit es leichter sichtbar ist:
[latex]<br />
c * n & \le & n - 3\sqrt n ~|~ :n<br />
c & \le & 1 - 3\frac{\sqrt n}{n}<br />
c -1 & \le & 1 - 3\frac{\sqrt n}{n}<br />
\frac{c -1}{3} & \le & \frac{\sqrt n}{n}<br />
[/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

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

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von bola: 05.01.2016 15:06.

05.01.2016 15:01 bola ist offline Beiträge von bola suchen Nehmen Sie bola in Ihre Freundesliste auf
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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

__________________
Syntax Highlighting fürs Board (Link)
05.01.2016 15:08 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
Karlito Karlito ist männlich
Kaiser


Dabei seit: 11.04.2011
Beiträge: 1.461

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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:14 Karlito ist offline E-Mail an Karlito senden Beiträge von Karlito suchen Nehmen Sie Karlito in Ihre Freundesliste auf
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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.

eulerscheZahl hat dieses Bild (verkleinerte Version) angehängt:
2016-01-05-152536_2560x1440_scrot.png



__________________
Syntax Highlighting fürs Board (Link)
05.01.2016 15:29 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
bola
Grünschnabel


Dabei seit: 05.01.2016
Beiträge: 5

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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
06.01.2016 00:31 bola ist offline Beiträge von bola suchen Nehmen Sie bola in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Theoretische Informatik » O Notation