O-Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Gesucht wird die Komplexität in O-Notation der Funktion [mm] N^{2} [/mm] + 2N + 11.
Finden Sie konkrete Werte für c und n0, so dass die Formel gilt:
f(n) = O (g(n)): [mm] \gdw \exists c,n_{0} \forall [/mm] n [mm] \ge n_{0} [/mm] : f(n) [mm] \le [/mm] c * g(n) |
Bitte um hilfe.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:49 Mo 19.01.2009 | | Autor: | bazzzty |
> Gesucht wird die Komplexität in O-Notation der Funktion
> [mm]N^{2}[/mm] + 2N + 11.
>
> Finden Sie konkrete Werte für c und n0, so dass die Formel
> gilt:
> f(n) = O (g(n)): [mm]\gdw \exists c,n_{0} \forall[/mm] n [mm]\ge n_{0}[/mm]
> : f(n) [mm]\le[/mm] c * g(n)
> Bitte um hilfe.
Es ist viel einfacher, Dir zu helfen, wenn Du dazuschreibst, was Du verstanden hast, und wo Du hängst.
Unabhängig davon ist die Aufgabe etwas sinnlos gestellt. Es gilt (wie immer) [mm]N^2+2N+11=O(N^2+2N+11)[/mm] mit [mm] $n_0=0$ [/mm] und $c=1$.
Interessant wäre zu zeigen, dass [mm]N^2+2N+11=O(N^2)[/mm], aber wenn das nicht explizit gefordert ist, könnte man genauso auch zeigen, dass[mm]N^2+2N+11=O(\pi N^2-100N+\log\log N)[/mm] (was auch stimmt).
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:19 Di 20.01.2009 | | Autor: | joschka92 |
Vilen dank!
|
|
|
|
