Ich brauche Euch für meine Info-Hausaufgaben

[crazychrisi]

Hi Ihr,

ich weiss zwar nicht ob ich hier richtig bin, aber ich bin schon so verzweifelt dass ich es einfach mal probiere.

Es geht um die O-Notation...
Unsere Aufgabe ist es herauszufinden was folgendes bedeutet:
f(x) = O(x²)
f(x) = Ω(x²)
f(x) = Θ(x²)

Und dann haben wir verschiedene Funktionen:
f1(x) = x
f2(x) = x²
f3(x) = x(x-1)
f4(x) = x²/2
f5(x) = xlog(zur basis 2) x
f6(x) = xlog(zur basis 10)x+10000

Jetzt sollen wir 4 Paare herausnehmen und vergleichen. Wie zb.
f1(x) = O(f4(x))
und das mit ja oder nein beantworten.

Ich weiss nicht mal was unser Prof von uns will..... Ich hoffe irgendjemand kann damit was anfangen und mir weiter helfen.
Vielen vielen Dank schon mal

LG Chrisi

[Greenhorn23]

als erstes muss ich sagen, hab ich keine ahnung was du da genau machen willst/musst, aber mein erster weg hat mich zu wikipeda geführt: http://de.wikipedia.org/wiki/O_Notation
bei den weblinks ganz unten stehen auch ne menge dinge drin, vielleicht hilft dir das weiter, denn du hast bestimmt schonmal was davon gehört und kannst mit den ganzen symbolen/formeln was anfangen

[Barney]

Ein Informatiker sollte die O-Notation eigentlich schon vor dem Studium kennen, kommt schließlich in fast jedem Artikel/Buch vor. Lies dir die PDF-Datei im Anhang des Wiki-Artikels durch, da ist es auf jeden Fall gut erklärt.

Gruß

[aphix]

Ein Informatiker sollte die O-Notation eigentlich schon vor dem Studium kennen

Vergessen oder nie gehört! Auf jeden Fall nie gebraucht !

[Cybergreek]

Ein Informatiker sollte die O-Notation eigentlich schon vor dem Studium kennen...

Naja, vor dem Studium ist ein bißchen übertrieben... Man soll ja schließlich während des Studium auch was lernen. Und die O-Notation fällt meistens in die ersten Wochen...

[Barney]

@aphix, Cybergreek: Leider darf ich auf eure Kommentare nicht kritisch antworten, da ich sonst wieder negativ bewertet werde (sowas wie Diskussionen kennt man hier wohl nicht). Daher: volle Zustimmung; warum habe ich bloß sowas Blödes davor geschrieben?!

[crazychrisi]

Vielen Dank für eure Beiträge
Habe es irgendwie selbst gelöst, ob es richtig ist wird sich noch rausstellen...

Und zu meiner Verteidigung, bin nur Lehramtstudentin und mein affines Fach ist Informatik.... Also keine Informatikstudentin Deswegen hab ich da auch so gut wie kein Plan von.

[Cybergreek]

@aphix, Cybergreek: Leider darf ich auf eure Kommentare nicht kritisch antworten, da ich sonst wieder negativ bewertet werde (sowas wie Diskussionen kennt man hier wohl nicht). Daher: volle Zustimmung; warum habe ich bloß sowas Blödes davor geschrieben?!

Also wegen mir musst Du Dich nicht zurückhalten. Wenn Du mir was zu sagen hast, dann sag es lieber direkt anstatt das in Dich hineinzufressen.

Was haben überhaupt die Bewertungen für eine Auswirkung?

[Hausmaster]

Sind gut fürs Ego , bzw. negativ Bewertungen, zuerst ist man ein Punkt grün, dann wird man grau und dann rot, am Ende wirst du gesperrt.

[Barney]

Vielen Dank für eure Beiträge
Habe es irgendwie selbst gelöst, ob es richtig ist wird sich noch rausstellen...

Ich bitte um die Lösung. Wenn du dir Mühe machst (was ich persönlich schätze), sind Verbesserungsvorschläge oder Erklärungen von unserer Seite aus alles andere als zu viel verlangt!

Und zu meiner Verteidigung, bin nur Lehramtstudentin und mein affines Fach ist Informatik.... Also keine Informatikstudentin Deswegen hab ich da auch so gut wie kein Plan von.

In diesem Fall bitte ich um Entschuldigung - ich hatte ein ganz anderes Bild von dir.

@Cybergreek: Offensichtlich komme ich hier unpassend rüber, weil ich, ohne jegliche Hintergedanken, andere Leute auf etwas hinweise und einige Mitglieder bisschen aufziehe.

So sollet ihr weiterhin nicken, ohne etwas in Frage zu stellen, um die hohlen Früchte zu ernten.

[Cybergreek]

@Cybergreek: Offensichtlich komme ich hier unpassend rüber, weil ich, ohne jegliche Hintergedanken, andere Leute auf etwas hinweise und einige Mitglieder bisschen aufziehe.

Naja, mir ist lieber, Du sagst mir direkt, was Dir an meinen Aussagen nicht passt bzw. warum Du anderer Meinung zu sein scheinst, anstatt mir das sehr indirekt vermitteln zu wollen.

Wenn Du Angst vor einer Diskussion hast (bzw. vor den Bewertungen), dann sprich es erst garnicht an. Ich finde, dass es so zu mehr Trara kommt...

[crazychrisi]

So hier meine Lösungen und bitte nicht lachen

Aufgabe 1: Finden Sie heraus, was folgendes bedeutet:
f(x) = O(x²) => Die Rechenzeit wächst quadratisch mit der Problemgröße und f(x) wächst höchstens so schnell wie x²
f(x) = Ω(x²) => f(x) wächst mindestens so schnell wie x²
f(x) = Θ(x²) => f(x) wächst genau so schnell wie x² und gilt wenn f(x) = O(x²) und f(x) = Ω(x²) zutreffen

Aufgabe 2:
f1(x) = x
f2(x) = x²
f3(x) = x(x-1)
f4(x) = x²/2
f5(x) = xlog(zur Basis 2) x
f6(x) = xlog(zur Basis 10) x + 10000
f7(x) = 3*2^x
f8(x) = 3^x

Vergleichen Sie Funktionen und beantworten Sie mit ja oder nein.
f1(x) = O(f4(x)) => ja
f4(x) = Ω(f1(x)) => ja
f2(x) = O(f1(x)) => nein
f2(x) = Ω(f1(x)) => ja
f7(x) = O(f8(x)) => ja
f7(x) = Ω(f8(x)) => nein
f7(x) = Θ(f8(x)) => nein

[Cybergreek]

Aufgabe 1: Finden Sie heraus, was folgendes bedeutet:
f(x) = O(x²) => Die Rechenzeit wächst quadratisch mit der Problemgröße und f(x) wächst höchstens so schnell wie x²
f(x) = Ω(x²) => f(x) wächst mindestens so schnell wie x²
f(x) = Θ(x²) => f(x) wächst genau so schnell wie x² und gilt wenn f(x) = O(x²) und f(x) = Ω(x²) zutreffen
...

Hier gilt, bei der ersten Aussage "... höchstens so schnell wie ein Vielfaches von x²". Analog bei der zweiten Aussage. Was zur Folge hat, dass bei der dritten Aussagen das "genau so schnell" nicht mehr stimmt, da das Wachstum von f(x) zwischen dem Wachstum von a*x² und dem von b*x² liegt...