O Notation |
mrkrispi94
Grünschnabel
Dabei seit: 04.01.2016
Beiträge: 1
|
|
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
|
|
04.01.2016 15:46 |
|
|
|
Es muss in n0 und c gefunden werden, sodass das für alle n >= n0 gilt.
Erweitern wir die Abschätzung:
für n >= 0.
n0=1 und c=1 erfüllt die Bedingung.
und wieder erfüllt n0=1 und c=1 die Bedingung.
Bei musst du die Ungleichung für beide Richtungen zeigen.
bei bleibt effektiv ein n im Zähler. Daher , da n eine obere Schranke gibt. Wenn es in ist, dann auch in , da n < n^2.
Gleichzeitig ist es in und (obere Schranke).
Wenn du und ankreuzt, kannst du auch gleich nehmen, per Definition.
macht einiges leichter.
__________________ Syntax Highlighting fürs Board (Link)
|
|
05.01.2016 12:23 |
|
|
bola
Grünschnabel
Dabei seit: 05.01.2016
Beiträge: 5
|
|
|
05.01.2016 14:16 |
|
|
bola
Grünschnabel
Dabei seit: 05.01.2016
Beiträge: 5
|
|
Wurde geändert inkl. geschweifter Klammern
|
|
05.01.2016 14:36 |
|
|
|
Nehmen wir deine Definition:
c=1 ist falsch gewählt, also versuchen wir was zwischen 0 und 1. z.B: 0.5
, 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 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Du kannst es so machen. Aber n muss nicht durch n0 ersetzt werden. Es muss nur gelten, dass für alle gilt. ist dabei auch abhängig davon, wie c gewählt ist.
Du kannst dazu weiter umformen, damit es leichter sichtbar ist:
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 .
Gruß,
Karlito
|
|
05.01.2016 15:00 |
|
|
bola
Grünschnabel
Dabei seit: 05.01.2016
Beiträge: 5
|
|
Zitat: |
Original von eulerscheZahl
Nehmen wir deine Definition:
c=1 ist falsch gewählt, also versuchen wir was zwischen 0 und 1. z.B: 0.5
, 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 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 für alle gilt. ist dabei auch abhängig davon, wie c gewählt ist.
Du kannst dazu weiter umformen, damit es leichter sichtbar ist:
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 .
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 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Zitat: |
Original von bola
Das ist der Punkt den ich nicht verstehe.
Kann man nicht einfach 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
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
Ich hoffe ich habe nicht noch mehr (Schussel)fehler gemacht.
Gruß,
Karlito
|
|
05.01.2016 15:14 |
|
|
bola
Grünschnabel
Dabei seit: 05.01.2016
Beiträge: 5
|
|
Bzgl. 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 |
|
|
|