# Big O - Komplexität Prüfen



## emma26 (6. Apr 2016)

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 (6. Apr 2016)

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

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


----------



## emma26 (6. Apr 2016)

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

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


----------



## mrBrown (6. Apr 2016)

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 (6. Apr 2016)

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, dass`lim(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 (6. Apr 2016)

Meniskusschaden hat gesagt.:


> 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, dass`lim(f(x)/x^2)`endlich 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 (6. Apr 2016)

mrBrown hat gesagt.:


> 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 (7. Apr 2016)

emma26 hat gesagt.:


> 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 (7. Apr 2016)

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 (7. Apr 2016)

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 (8. Apr 2016)

Meniskusschaden hat gesagt.:


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



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.



emma26 hat gesagt.:


> 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ür `0<x<1` sind deine Zwischschritte falsch. Du musst schon wenigstens `x>=1` fordern.


----------



## stg (8. Apr 2016)

Meniskusschaden hat gesagt.:


> 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 (8. Apr 2016)

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.


----------

