Big O - Komplexität Prüfen

[emma26]

Hallo, habe grade mein Informatik studium begonnen und habe als HÜ (AlgoDat) dieses Aufgabenstellung!

f(x)= 5X^3+5-1, show that f(x) is O(x2)

Leider stehe ich gerade total am Schlauch, kann mir villeicht jemand helfen? ich finde keinen Ansatz!

LG Danke

 

[mrBrown]

Habt ihr irgendwelche Infos bekommen, welche Komplexität Multiplikation und Addition haben?

Ist mit O(x2) O(x^2) gemeint?

 

[emma26]

Ja sorry es ist O(x^2)!!!

nein, hab jetzt nochmal im Skript geschaut ob ich was übersehen habe!

 

[mrBrown]

Möglicherweise wird die Komplexität von x*x als O(x) gesehen (x-mal x aufsummieren), und für Addition ist es O(1).

Reicht dir das als Ansatz?

 

[Meniskusschaden]

Also für mich ist die ursprüngliche Behauptung falsch, aber vielleicht verstehe ich auch nicht richtig, was gemeint ist. Leider sind meine Mathe-Kenntnisse etwas eingestaubt, aber müsste man zur Bestätigung der Behauptung nicht nachweisen, dasslim(f(x)/x^2)endlich ist?

lim( (5x^3+5-1)/(x^2) )
= lim( 5x^3/x^2 + 5/x^2 - 1/x^2)
= lim( 5x + 5/x^2 - 1/x^2
= lim(5x) + lim(5/x^2) - lim(1/x^2)
= unendlich + 0 - 0

Es gibt demnach keinen endlichen Grenzwert, also ist f(x) nicht O(x^2). Bin leider nicht ganz sicher, ob das wirklich mathematisch korrekt ist.

 

[mrBrown]

Also für mich ist die ursprüngliche Behauptung falsch, aber vielleicht verstehe ich auch nicht richtig, was gemeint ist. Leider sind meine Mathe-Kenntnisse etwas eingestaubt, aber müsste man zur Bestätigung der Behauptung nicht nachweisen, dasslim(f(x)/x^2)endlich ist?

lim( (5x^3+5-1)/(x^2) )
= lim( 5x^3/x^2 + 5/x^2 - 1/x^2)
= lim( 5x + 5/x^2 - 1/x^2
= lim(5x) + lim(5/x^2) - lim(1/x^2)
= unendlich + 0 - 0

Es gibt demnach keinen endlichen Grenzwert, also ist f(x) nicht O(x^2). Bin leider nicht ganz sicher, ob das wirklich mathematisch korrekt ist.

Dürfte stimmen, je nachdem wie die Aufgabe gemeint ist.

Ich ab das jetzt einfach aufgefasst als Berechnen der Komplexität des Ausrechnens...

 

[Meniskusschaden]

Ich ab das jetzt einfach aufgefasst als Berechnen der Komplexität des Ausrechnens...

Könnte auch sein. Verstehe jetzt erst, was du gemeint hast.

 

[Xyz1]

f(x)= 5X^3+5-1, show that f(x) is O(x2)

Ja ist es. Warum es so ist, musst du jetzt zeigen. (scnr)

 

[emma26]

Hallo zusammen, ja bei hab heute mit meinen Mitstudenten gesprochen, bei komplexeren Aufgaben (zB. log in der Gleichung) kann man sich über dem lim annähern.

Hab auch gesehen dass ich mich verschrieben haben :
f(x)= 5X^3+5-1, show that f(x) is O(x^3) - SORRY .... sollte total verwirrt, verzweifelt nix ins Forum stellen

Aber bei dieser Aufgabe ist es viel einfacher hab auch viel zu komplitziert gedacht!!

Bei Big O kann man ja alles bis auf den größten Term und Zahlenwerte streichen somit bleibt O(x^3) die Aussage ist also wahr!!

Hab dann heute noch den Prof angesprochen und er meinte so gehts auch aber er will die Zwischenschritte und haben dann diese Lösung erarbeitet:

f(x)=|5x^3+4|
|f(x)| ≤ |5x^3|+|4|
|f(x)| ≤ 5x^3+4x^3 für alle x > 0
|f(x)| ≤ 9x^3 für alle x > 0
=> O(f(x)) = O(x^3)

LG

 

[Meniskusschaden]

Ja, so ergibt es einen Sinn. Aber vor Korrektur des Tippfehlers, also für die Prüfung f(x)=O(x^2) hätte ich keine einfachere Lösung als die Grenzwertbetrachtung gewusst, es sei denn O(X^3)!=O(x^2) darf ohne Beweis benutzt werden.

 

[stg]

lim( (5x^3+5-1)/(x^2) )
= lim( 5x^3/x^2 + 5/x^2 - 1/x^2)
= lim( 5x + 5/x^2 - 1/x^2
= lim(5x) + lim(5/x^2) - lim(1/x^2)
= unendlich + 0 - 0

Genauer muss man eigentlich den Limes Superior, also den lim sup betrachten.
Das vorletzte Gleichheitszeichen ist formal falsch. Du darfst den Grenzwert nur "auseinander ziehen", wenn alle beteiligten Grenzwerte existieren, das ist hier aber nicht der Fall.
Am Resultat ändert das alles allerdings nichts.

Hallo zusammen, ja bei hab heute mit meinen Mitstudenten gesprochen, bei komplexeren Aufgaben (zB. log in der Gleichung) kann man sich über dem lim annähern.

Auch hier: Eine einfache Grenzwertbetrachtung kann u.U. zum Ziel führen, aber eigentlich ist der lim sup zu betrachten. Jede andere Vorgehensweise, auch die aus deiner nachfolgenden Lösung, bedarf (sofern noch nicht in der Übungs oder Vorlesung erarbeitet) wenigstens einer Begründung, wieso man das in diesem Fall so machen darf.

Hab dann heute noch den Prof angesprochen und er meinte so gehts auch aber er will die Zwischenschritte und haben dann diese Lösung erarbeitet:
f(x)=|5x^3+4|
|f(x)| ≤ |5x^3|+|4|
|f(x)| ≤ 5x^3+4x^3 für alle x > 0
|f(x)| ≤ 9x^3 für alle x > 0
=> O(f(x)) = O(x^3)

Für 0<x<1 sind deine Zwischschritte falsch. Du musst schon wenigstens x>=1 fordern.

 

[stg]

für die Prüfung f(x)=O(x^2) hätte ich keine einfachere Lösung als die Grenzwertbetrachtung gewusst, es sei denn O(X^3)!=O(x^2) darf ohne Beweis benutzt werden.

Die Aussage kann mit einem Einzeiler bewiesen werden, aber das würde trotzdem nichts nützen. Nur weil f in O(x^3) liegt heißt das noch lange nicht, dass f nicht auch in O(x^2) liegen kann,

 

[Xyz1]

Ich dachte genau wie die anderen auch, es geht um die Laufzeit, die ein Rechner benötigt, Terme dieser Gestalt (ganzrationale Funktionen 3-ten Gerades) zu berechnen.
Du hast dich da mehrdeutig und sogar "falsch" geschrieben.