O Notation < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:51 Mo 08.02.2010 | | Autor: | etoxxl |
| Aufgabe | Ist die Aussage wahr oder falsch?
f(n) = 10 + n + 2log n -> f [mm] \in [/mm] O(n) |
Ich würde die Aufgaben so lösen:
1 Variante:
f(n) = 10 + n + 2log n <= 10n + n + 2n = 13n für n>= [mm] n_0 [/mm] = 1
Also [mm] \exists [/mm] n, [mm] n_0 \in \IN [/mm] und c = 13 mit n>= [mm] n_0 [/mm] und f(n)<=c*n
und damit f [mm] \in [/mm] O(n). => Aussage wahr
2 Variante:
f(n) = 10 + n + 2log n
10 [mm] \in [/mm] O(1) [mm] \in [/mm] O(n)
n [mm] \in [/mm] O(n)
2logn [mm] \in [/mm] O(log n) [mm] \in [/mm] O(n)
und damit f(n) [mm] \in [/mm] O(n) => Aussage wahr
Sind die beiden Varianten ok?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:06 Mo 08.02.2010 | | Autor: | felixf |
Moin!
> Ist die Aussage wahr oder falsch?
> f(n) = 10 + n + 2log n -> f [mm]\in[/mm] O(n)
>
> Ich würde die Aufgaben so lösen:
>
> 1 Variante:
> f(n) = 10 + n + 2log n <= 10n + n + 2n = 13n für n>= [mm]n_0[/mm]
> = 1
> Also [mm]\exists[/mm] n, [mm]n_0 \in \IN[/mm] und c = 13 mit n>= [mm]n_0[/mm] und
> f(n)<=c*n
> und damit f [mm]\in[/mm] O(n). => Aussage wahr
![[ok]](/images/smileys/ok.gif "[ok]")
> 2 Variante:
> f(n) = 10 + n + 2log n
> 10 [mm]\in[/mm] O(1) [mm]\in[/mm] O(n)
> n [mm]\in[/mm] O(n)
> 2logn [mm]\in[/mm] O(log n) [mm]\in[/mm] O(n)
> und damit f(n) [mm]\in[/mm] O(n) => Aussage wahr
Wenn du hier das [mm] $\in$ [/mm] bei $O(1) [mm] \in [/mm] O(n)$, [mm] $O(\log [/mm] n) [mm] \in [/mm] O(n)$ durch [mm] $\subseteq$ [/mm] oder so ersetzt, stimmt es.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:08 Mo 08.02.2010 | | Autor: | etoxxl |
alles klar, danke!
|
|
|
|
