verhalten von funktionen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:54 Do 19.07.2007 | | Autor: | AriR |
hey leute
wenn ich funktionen betrachte und deren komplexität, dann ist das bei polynomen ja eine recht einfache sache.
wenn mann ein polynom hat, dann liegt deren komplexität immer [mm] x^\lambda [/mm] wobei [mm] \lambda [/mm] der grad der funktion ist.
was passiert aber genau bei funktionen wie beispielsweise
[mm] x*\wurzel(x), x^2+log(x) [/mm] oder x*log(x)
bei [mm] x^2+log(x) [/mm] würde ich sagen, ist das immer noch [mm] O(x^2), [/mm] da log langsamer wächst als jedes polynom und somit zB gilt
[mm] x^2+log(x)\le x^2+x \le x^2
[/mm]
bei [mm] x*\wurzel(x) [/mm] dachte ich könnte man das vllt so umschreiben:
[mm] x*x^0,5=x^{1,5} [/mm] und das liegt in [mm] O(x^{1,5})
[/mm]
kann das?
bei der sache mit dem x*log(x) habe ich keine ahnung.
würde sagen das liegt wieder einfach in O(x*log(x))
wäre echt super, wenn mir heute hier jemand weiterhelfen könnte.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:42 Do 19.07.2007 | | Autor: | dormant |
Hi!
Erstmal die formale Definition:
f(x) ist O(g(x)), wenn [mm] \exists x_{0}, [/mm] M, so dass [mm] |f(x)|\le [/mm] M*|g(x)| für alle [mm] x\ge x_{0}.
[/mm]
> bei [mm]x^2+log(x)[/mm] würde ich sagen, ist das immer noch [mm]O(x^2),[/mm]
> da log langsamer wächst als jedes polynom und somit zB
Das stimmt, aber
> gilt
> [mm]x^2+log(x)\le x^2+x \le x^2[/mm]
diese Abschätzung ist leider falsch. Es gilt eher, dass
[mm] |x^{2}+\ln(x)|\le |x^{2}+x^{2}|\le 2x^{2}. [/mm] Somit wählt man M als 2 und [mm] g(x):=x^{2}
[/mm]
> bei [mm]x*\wurzel(x)[/mm] dachte ich könnte man das vllt so
> umschreiben:
>
> [mm]x*x^0,5=x^{1,5}[/mm] und das liegt in [mm]O(x^{1,5})[/mm]
>
> kann das?
Das gilt trivialerweise, da in diesem Fall ist g(x)=f(x) und M=1.
> bei der sache mit dem x*log(x) habe ich keine ahnung.
>
> würde sagen das liegt wieder einfach in O(x*log(x))
Da [mm] \ln(x)\le [/mm] x, kann man auch [mm] O(x^{2}) [/mm] wählen. Das ist aber eine zu großzüge Abschätzung und deswegen ist es vielleicht angebracht wieder die triviale Abschätzung [mm] O(x\ln(x)) [/mm] zu wählen.
Gruß,
dormant
|
|
|
|
