Laufzeiten < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:11 Do 12.01.2012 | | Autor: | gloomy |
| Aufgabe | | Zeigen Sie, dass die Gleichung [mm] $An^2 [/mm] + Bn + C = [mm] \mathcal{O}(n^2)$ [/mm] für beliebige $A,B,C [mm] \in \mathbb{R}$ [/mm] gilt. |
Kann mir jemand bei der Aufgabe helfen?
Also ich weiß ja, dass [mm] $\mathcal{O}(g(n)) [/mm] = [mm] \{ f : \exists c > 0, n_0>0: \forall n > n_0: f(n) \leq c g(n) \}. [/mm] Aber wie hilft mir das weiter bei der Aufgabe?
Kann ich einfach sagen, es gilt:
[mm] $An^2 [/mm] + Bn + C [mm] \leq dn^2 \Rightarrow A+\frac{B}{n}+\frac{C}{n^2} \leq [/mm] d$ und dann?
Vielen Dank für eure Hilfe.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:56 Do 12.01.2012 | | Autor: | felixf |
Moin!
> Zeigen Sie, dass die Gleichung [mm]An^2 + Bn + C = \mathcal{O}(n^2)[/mm]
> für beliebige [mm]A,B,C \in \mathbb{R}[/mm] gilt.
> Kann mir jemand bei der Aufgabe helfen?
> Also ich weiß ja, dass [mm]$\mathcal{O}(g(n))[/mm] = [mm]\{ f : \exists c > 0, n_0>0: \forall n > n_0: f(n) \leq c g(n) \}.[/mm]
> Aber wie hilft mir das weiter bei der Aufgabe?
>
> Kann ich einfach sagen, es gilt:
> [mm]An^2 + Bn + C \leq dn^2 \Rightarrow A+\frac{B}{n}+\frac{C}{n^2} \leq d[/mm]
> und dann?
Fuer $n [mm] \ge [/mm] 1$ gilt $1 [mm] \le [/mm] n [mm] \le n^2$, [/mm] und damit $A [mm] n^2 [/mm] + B n + C [mm] \le [/mm] (|A| + |B| + |C|) [mm] n^2$. [/mm] Also, wie kannst du die Konstanten $c$ und [mm] $n_0$ [/mm] waehlen, damit $A [mm] n^2 [/mm] + B n + C$ in [mm] $\mathcal{O}(n^2)$ [/mm] liegt?
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:05 Fr 13.01.2012 | | Autor: | gloomy |
> Moin!
>
> > Zeigen Sie, dass die Gleichung [mm]An^2 + Bn + C = \mathcal{O}(n^2)[/mm]
> > für beliebige [mm]A,B,C \in \mathbb{R}[/mm] gilt.
> > Kann mir jemand bei der Aufgabe helfen?
> > Also ich weiß ja, dass [mm]$\mathcal{O}(g(n))[/mm] = [mm]\{ f : \exists c > 0, n_0>0: \forall n > n_0: f(n) \leq c g(n) \}.[/mm]
> > Aber wie hilft mir das weiter bei der Aufgabe?
> >
> > Kann ich einfach sagen, es gilt:
> > [mm]An^2 + Bn + C \leq dn^2 \Rightarrow A+\frac{B}{n}+\frac{C}{n^2} \leq d[/mm]
> > und dann?
>
> Fuer [mm]n \ge 1[/mm] gilt [mm]1 \le n \le n^2[/mm], und damit [mm]A n^2 + B n + C \le (|A| + |B| + |C|) n^2[/mm].
> Also, wie kannst du die Konstanten [mm]c[/mm] und [mm]n_0[/mm] waehlen, damit
> [mm]A n^2 + B n + C[/mm] in [mm]\mathcal{O}(n^2)[/mm] liegt?
>
> LG Felix
>
Also kann ich $ [mm] n_0 [/mm] = 1 $ und $c = (|A| + |B| + |C|) $ wählen?!
Danke für die Antwort.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:50 Sa 14.01.2012 | | Autor: | felixf |
Moin!
> > > Zeigen Sie, dass die Gleichung [mm]An^2 + Bn + C = \mathcal{O}(n^2)[/mm]
> > > für beliebige [mm]A,B,C \in \mathbb{R}[/mm] gilt.
> > > Kann mir jemand bei der Aufgabe helfen?
> > > Also ich weiß ja, dass [mm]$\mathcal{O}(g(n))[/mm] = [mm]\{ f : \exists c > 0, n_0>0: \forall n > n_0: f(n) \leq c g(n) \}.[/mm]
> > > Aber wie hilft mir das weiter bei der Aufgabe?
> > >
> > > Kann ich einfach sagen, es gilt:
> > > [mm]An^2 + Bn + C \leq dn^2 \Rightarrow A+\frac{B}{n}+\frac{C}{n^2} \leq d[/mm]
> > > und dann?
> >
> > Fuer [mm]n \ge 1[/mm] gilt [mm]1 \le n \le n^2[/mm], und damit [mm]A n^2 + B n + C \le (|A| + |B| + |C|) n^2[/mm].
> > Also, wie kannst du die Konstanten [mm]c[/mm] und [mm]n_0[/mm] waehlen, damit
> > [mm]A n^2 + B n + C[/mm] in [mm]\mathcal{O}(n^2)[/mm] liegt?
>
> Also kann ich [mm]n_0 = 1[/mm] und [mm]c = (|A| + |B| + |C|)[/mm] wählen?!
Versuch damit doch mal einen sauberen Beweis fuer die Aussage aufzuschreiben. Wenn es klappt, dann war das offenbar richtig, oder?
LG Felix
|
|
|
|
