Beweis O-Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Ist [mm] \frac{n^3+n+1}{2n^2-5} [/mm] in [mm] \mathcal{O}(n) [/mm] |
Hab folgendes gemacht:
[mm] \frac{n^3+n+1}{2n^2-5} \leq [/mm] c*n
[mm] \frac{\frac{n^3+n+1}{2n^2-5}}{n} \leq [/mm] c
[mm] \frac{n^3+n+1}{2n^3-5n} \leq [/mm] c
Wenn ich nun [mm] \limes_{n\rightarrow\infty} [/mm] mache bekomme ich als Grenzwert [mm] \frac{1}{2}.
[/mm]
Reicht das oder muss ich da noch weitermachen? Also [mm] \frac{1}{2} \leq [/mm] c.
Gruss
|
|
| |
|
Hallo royalbuds,
> [mm]\frac{n^3+n+1}{2n^3-5n} \leq[/mm] c
Hier kannst du abschätzen:
[mm]\frac{n^3+n+1}{2n^3-5n} \le \frac{n^3+2n}{2n^3-5n} = \frac{n^2+2}{2n^2-5}=\frac{1+\frac{2}{n^2}}{2-\frac{5}{n^2}}[/mm]
Der Bruch wird größer, wenn der Zähler wächst und der Nenner kleiner wird. Gleichzeitig muß der Bruch > 0 sein. Also muß [mm]2-\tfrac{5}{n^2}>0\Rightarrow n^2 > 2.5[/mm] gelten, was erst für [mm]n\ge 2[/mm] gilt. Da jedes [mm]n>2\![/mm] den Zähler kleiner und den Nenner größer macht, ist [mm]\tfrac{1+\frac{1}{2}}{2-\frac{5}{4}}=2[/mm] die gesuchte Schranke:
[mm]\frac{n^3+n+1}{2n^3-5n}\le 2\quad\forall n\in \mathbb{N}_{\ge 2}.[/mm]
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:51 Do 27.11.2008 | | Autor: | bazzzty |
> Ist [mm]\frac{n^3+n+1}{2n^2-5}[/mm] in [mm]\mathcal{O}(n)[/mm]
> Hab folgendes gemacht:
>
> [mm]\frac{n^3+n+1}{2n^2-5} \leq[/mm] c*n
>
> [mm]\frac{\frac{n^3+n+1}{2n^2-5}}{n} \leq[/mm] c
>
> [mm]\frac{n^3+n+1}{2n^3-5n} \leq[/mm] c
>
> Wenn ich nun [mm]\limes_{n\rightarrow\infty}[/mm] mache bekomme ich
> als Grenzwert [mm]\frac{1}{2}.[/mm]
Das reicht prinzipiell, aber es bleibt in meinen Augen etwas unsauber: Es gibt nicht explizit ein [mm]c[/mm], und erst recht kein [mm]n_0[/mm].
> Reicht das oder muss ich da noch weitermachen? Also
> [mm]\frac{1}{2} \leq[/mm] c.
Das wiederum stimmt nicht, denn [mm]c=1/2[mm] geht nicht:
Für alle [mm]n[/mm] ist [mm]\frac{n^3+n+1}{2n^2-5}>\frac{1}{2}n[/mm]. Du mußt [mm]c[/mm] schon echt größer wählen.
Wegen der mathematischen Ungenauigkeiten bin ich kein Freund von diesen Grenzwertspielereien. Es geht eigentlich immer einfacher:
[mm]\frac{n^3+n+1}{2n^2-5}\leq\frac{3n^3}{2n^2-5}[/mm] für alle [mm]n[/mm] und [mm]\frac{3n^3}{2n^2-5}\leq \frac{3n^3}{n^2}\leq 3n[/mm] für [mm]n\geq 5[/mm].
Und fertig ist es.
|
|
|
|
