Landau-Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:27 Fr 10.05.2013 | | Autor: | Naienna |
| Aufgabe | Ordnen Sie die folgenden Funktionen F1,...,F12 nach der Größenordnung ihres Wachstums, dass heißt: finden Sie eine Folge i1,...,i12 so, dass Fij [mm] \in [/mm] O(Fij+1) gilt für j=1,...,11:
F1:n [mm] \mapsto [/mm] n²
F2:n [mm] \mapsto [/mm] n!
F3:n [mm] \mapsto (3/2)^{n}
[/mm]
F4:n [mm] \mapsto [/mm] n³
F5:n [mm] \mapsto (log_{2}n)²
[/mm]
F6:n [mm] \mapsto n2^{n}
[/mm]
F7:n [mm] \mapsto log_{2}n
[/mm]
F8:n [mm] \mapsto [/mm] 1
F9:n [mm] \mapsto [/mm] n
F10:n [mm] \mapsto 2^{n}
[/mm]
F11:n [mm] \mapsto [/mm] n [mm] log_{2}n
[/mm]
F12:n [mm] \mapsto [/mm] n² [mm] log_{2}n
[/mm]
Es sind dabei keine Beweise gefordert. |
Hallo wir haben uns eine Reihenfolge überlegt, indem wir die Definition der O-Notation benutzt haben, wobei wir c meistens auf 2 gesetzt haben und [mm] n_{0} [/mm] auf 1. Wär cool wenn ihr einmal drüber schauen könntet und uns ggf. auf Fehler aufmerksam machen würdet :)
F8 [mm] \le [/mm] F7 [mm] \le [/mm] F5 [mm] \le [/mm] F9 [mm] \le [/mm] F11 [mm] \le [/mm] F1 [mm] \le [/mm] F12 [mm] \le [/mm] F4 [mm] \le [/mm] F3 [mm] \le [/mm] F10 [mm] \le [/mm] F6 [mm] \le [/mm] F2
Vielen Dank :)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:28 Mo 13.05.2013 | | Autor: | felixf |
Moin!
> Ordnen Sie die folgenden Funktionen F1,...,F12 nach der
> Größenordnung ihres Wachstums, dass heißt: finden Sie
> eine Folge i1,...,i12 so, dass Fij [mm]\in[/mm] O(Fij+1) gilt für
> j=1,...,11:
>
> F1:n [mm]\mapsto n^2[/mm]
> F2:n [mm]\mapsto[/mm] n!
> F3:n [mm]\mapsto (3/2)^{n}[/mm]
> F4:n [mm]\mapsto n^3[/mm]
> F5:n [mm]\mapsto (log_{2}n)^2[/mm]
> F6:n [mm]\mapsto n2^{n}[/mm]
> F7:n
> [mm]\mapsto log_{2}n[/mm]
> F8:n [mm]\mapsto[/mm] 1
> F9:n [mm]\mapsto[/mm] n
> F10:n [mm]\mapsto 2^{n}[/mm]
> F11:n [mm]\mapsto[/mm] n [mm]log_{2}n[/mm]
> F12:n [mm]\mapsto n^2 log_{2}n[/mm]
>
> Es sind dabei keine Beweise gefordert.
> Hallo wir haben uns eine Reihenfolge überlegt, indem wir
> die Definition der O-Notation benutzt haben, wobei wir c
> meistens auf 2 gesetzt haben und [mm]n_{0}[/mm] auf 1. Wär cool
> wenn ihr einmal drüber schauen könntet und uns ggf. auf
> Fehler aufmerksam machen würdet :)
>
> F8 [mm]\le[/mm] F7 [mm]\le[/mm] F5 [mm]\le[/mm] F9 [mm]\le[/mm] F11 [mm]\le[/mm] F1 [mm]\le[/mm] F12 [mm]\le[/mm] F4 [mm]\le[/mm]
> F3 [mm]\le[/mm] F10 [mm]\le[/mm] F6 [mm]\le[/mm] F2
Die Reihenfolge stimmt so.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:44 Mo 13.05.2013 | | Autor: | Naienna |
Richtig gut, dankeschön Felix! 
|
|
|
|
