O-Notation

Neue Frage »

kleeblatt Auf diesen Beitrag antworten »
O-Notation
Hallo!

Ich hab folgende Aufgabe bekommen:

"Beweisen oder widerlegen Sie:
O(8^n) = 3^(O(n))
Schreiben Sie hier zuerst formal auf was das bedeutet."

Bis jetzt hatte ich nur Beispiele zur O-Notation wo ich einen Funktion f(x) und eine Funktion g(x) hatte und mit der Definition der O-Notation (http://de.wikipedia.org/wiki/Landau-Symbole) auskam...
Doch was mach ich bei diesem Beispiel???

Danke für eure Antworten!!!
AD Auf diesen Beitrag antworten »

Ich weiß nicht, ob die Schreibweise



so richtig offiziell ist - nach meinem Empfinden bedarf die noch einer Erklärung, etwas in der Art:

Für jede Funktion gilt und für jede Funktion gilt .

Wenn das so zu verstehen sein soll, dann empfehle ich dir, nach einem Gegenbeispiel (also einem konkreten oder ) zu suchen, was den angesprochenen Forderungen nicht genügt.
kleeblatt Auf diesen Beitrag antworten »

ich hab nur das oben genannte als Aufgabenstellung und diese soll ich begründen...

danke für deine antwort...ich versteh sie nur leider nicht :-(
AD Auf diesen Beitrag antworten »

Es war eine Aufforderung an dich, die Notation zu erklären, die ist mir nämlich im Gegensatz zu den üblichen Landau-Symbolen noch nie untergekommen. unglücklich

Eine mögliche Erklärung für eine streng monoton wachsende Funktion wäre

,

genauso habe ich es in meinem letzten Beitrag gemutmaßt.

Ich warte auf deine Bestätigung/Ablehnung dieser Interpretation. Dein luthersches "Ich-stehe-hier-und-kann-nicht-anders" ist da gar nicht hilfreich, denn du solltest dich schon bemühen, die Notation eurer Aufgabenstellungen zu verstehen. Bei solchen Unklarheiten sollte man auch mal beim Aufgabensteller (Prof/Assi) nachfragen!
kleebatt Auf diesen Beitrag antworten »

ich weiß leider wirklich nicht wie ich die Aufgarbe deuten soll (das ist übrigens Teil der Aufgabe...) dewegn hab ich mir gedacht ich frag mal...vl kennt sich ja jemand mit dieser Schreibweise aus...

weiters kannst du glaube ich nicht urteilen in wie weit ich mich damit schon auseinander gesetzt hab...
und Hilfestellung gibt es keine...da wir uns es ja selbst überlegn sollen!!!

so zu meinen Überlegungen:
O(8^n) steht für eine Fkt der en Komplexitätsklasse gleich O(8^n) ist. dh für eine bel Fkt f(n) gilt f(n) = O(8^n), und weiters muss gelten f(n)= 3^(O(n)). D.h ich will zeigen, dass die Menge der Fkt die O(8^n) sind eine Teilmenge der menge 3^(O(n)) ist.
Jetzt hab ich mir jetz so eine Funktion gesucht für die das zutrifft: zB x^8+x^4-2

weiter bin ich noch nicht gekommen...
WebFritzi Auf diesen Beitrag antworten »

Zitat:
Original von kleebatt
weiters kannst du glaube ich nicht urteilen in wie weit ich mich damit schon auseinander gesetzt hab...


Doch, das kann er. Allein die Tatsache, dass du f(O(n)) nicht definieren kannst, spricht Bände. Zudem bekommt man das Gefühl, dass du gar nicht verstehst, um was es Arthur Dent geht.


Zitat:
Original von kleebatt
und Hilfestellung gibt es keine...da wir uns es ja selbst überlegn sollen!!!


Das geht aber schlecht, wenn eine Definition fehlt. Also nochmals die Frage: Was bedeutet ?
 
 
thom01 Auf diesen Beitrag antworten »

ohje!

es gibt bei disem beispiel KEINE Hilfestellung!
Es wurden einfach nur die Beispiele ausgegeben und dann ist es zu machen! Punkt aus!
Kennt man sich mit diesem Gebiet aber besser aus, so kann man sehr wohl sagen wie das zu Beweisen oder zu wiederlegen ist! Das ist doch lächerlich!
Sich hier nur groß aufspielen und behaupten dass sich der anderen nicht wirklich auskennt ist wirklich intelligent!
Natürlich kennt er sich nicht wirklich aus sonst hätte er nicht hier nachfragen müssen!
Anstatt ihm einfach zu helfen bzw. zu sagen wie es sein könnte und dann aufgrund dieser VERMUTUNG weiter zu helfen kommen nur überhebliche, tolle sprüche daher im still von "ich kann es aber wenn du nicht so tust als ob du es auch kannst, sag ich nix!"


Und ich brauch jetzt niemanden der sich motiviert fühlt mit mir zu streiten, interessiert mich wirklich einen scheiss!
Denkt mal darüber nach!
Jacques Auf diesen Beitrag antworten »

Hallo,

Dann erklär Du doch jetzt die Schreibweise, wenn Du schon den längst erledigten Thread für eine große Anklage ausgräbst. Augenzwinkern



Zitat:
Original von thom01

Kennt man sich mit diesem Gebiet aber besser aus, so kann man sehr wohl sagen wie das zu Beweisen oder zu wiederlegen ist!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »