Laufzeit von Funktionen ordnen < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:21 Sa 21.10.2006 | | Autor: | dump_0 |
| Aufgabe | Finden Sie eine Reihenfolge [tex]f_1 \in O(f_2), f_2 \in O(f_3), ...[/tex] für die Funktionen
[tex]\wurzel{log(5n)}, log(n!), n^{logn}, log^{2}n, loglogn, n^{1 / log_{7}n}, (logn)^{logn}[/tex]
Beweisen Sie Ihre Aussage! |
Wie geht man hier zur Lösung vor? Soll ich etwa mit den verschiedenen Graphen argumentieren oder muss ich hier etwa Grenzwerte berechnen?
Ich habe leider absolut keine Ahnung was ich hier genau tun soll.
Hilfe wäre sehr nett.
Grüße
|
|
| |
|
Hallo und guten Tag,
> Finden Sie eine Reihenfolge [tex]f_1 \in O(f_2), f_2 \in O(f_3), ...[/tex]
> für die Funktionen
>
> [tex]\wurzel{log(5n)}, log(n!), n^{logn}, log^{2}n, loglogn, n^{1 / log_{7}n}, (logn)^{logn}[/tex]
>
Es ist hier nicht zeichnerisch, sondern formal entlang der Definition der O-Notation zu argumentieren.
Hilfreich sind dabei solche Regeln wie
(1) Falls f und g Funktionen von [mm] \IN [/mm] nach [mm] \IN [/mm] sind und c eine Konstante, so dass für fast alle n gilt:
[mm] f(n)\leq [/mm] g(n)+c
so folgt [mm] 2^{f(n)}\: =\: O(2^{g(n)}
[/mm]
(2) Falls c>0 existiert mit [mm] f(n)\leq g(n)^c [/mm] für fast alle n, so gilt
[mm] \log [/mm] (f(n))=O(log (g(n))
Wenn Du (1) und (2) benutzen möchtest und Ihr das noch nicht hattet, musst Du es natürlich erst einmal beweisen - aber halt nur
einmal allgemein und nicht für jedes Paar von Funktionen neu.
Gruss,
Mathias
> Beweisen Sie Ihre Aussage!
> Wie geht man hier zur Lösung vor? Soll ich etwa mit den
> verschiedenen Graphen argumentieren oder muss ich hier etwa
> Grenzwerte berechnen?
> Ich habe leider absolut keine Ahnung was ich hier genau
> tun soll.
>
> Hilfe wäre sehr nett.
>
> Grüße
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:56 Mo 23.10.2006 | | Autor: | dump_0 |
Hallo Mathias!
Also auf Anfrage bekam ich von einem Tutor die Antwort, wie sollen die entsprechenden Konstanten c und die [mm] n_0 [/mm] finden, sodass die entsprechenden Beziehungen gelten.
In der Vorlesung hatten wir folgendes Beispiel:
[tex]f(n) = n^2 + 1000n[/tex]
Zu zeigen: [tex]f(n) = O(n^2)[/tex]
Gesucht war also ein [tex]c >0, n_0 \in \IN: \forall n \ge n_0: f(n) \le cg(n)[/tex]
Der Prof. nahm dafür:
[tex]f(n) = n^2 + 1000n \le n^2 + 1000n^2 = 1001n^2[/tex]
[tex]\Rightarrow c = 1001, n_0 = 1[/tex]
Das Beispiel ist einleuchtend.
Die einzelnen Defintionen für O, [mm] \Omega [/mm] und [mm] \Theta [/mm] haben wir auch behandelt.
Jedoch weiß ich jetzt trotzdem nicht wie ich auf die einzelnen Konstanten und [mm] n_0 [/mm] komme.
Nehmen wir z.B. mal
[tex]f(n) = n^{1 / log_{7}n} = O(n^{logn})[/tex]
Ja, aber wie beweise ich jetzt, dass das auch so ist? Ich finde leider keine Konstante und kein [mm] n_0 [/mm] :(
Grüße
|
|
|
| |
|
Hallo und guten Morgen,
>
> Nehmen wir z.B. mal
>
> [tex]f(n) = n^{1 / log_{7}n} = O(n^{logn})[/tex]
>
> Ja, aber wie beweise ich jetzt, dass das auch so ist? Ich
> finde leider keine Konstante und kein [mm]n_0[/mm] :(
>
> Grüße
f(n) = [mm] n^{1 / log_{7}n}=n^{1\slash (\log (n)\log (7))}=n^{\frac{\log (7)}{\log (n)}}
[/mm]
und nun gibt es sicher [mm] n_0, [/mm] so dass für alle [mm] n\geq n_0 [/mm]
[mm] \log (n)\geq\frac{\log (7)}{\log (n)}
[/mm]
gilt (ich nehme an, dass [mm] \log [/mm] der Zweierlogarithmus ist, sonst muss man es halt zur gemeinten Basis (zB 10) rechnen),
zB [mm] n\geq 2^{\sqrt{\log 7}}
[/mm]
Für diese n ist dann also [mm] f(n)\leq n^{\log n}
[/mm]
und somit kannst Du [mm] n_0=\left\lcei2^{\sqrt{\log 7}}\right\rceil
[/mm]
und c=1 nehmen.
Wichtig ist: Du musst jeweils nicht das ''beste'', also das kleinste [mm] n_0 [/mm] finden, sondern einfach irgendein [mm] n_0 [/mm] und irgendein c, so dass es gilt,
und dies ist schön, denn es erlaubt Dir im allgemeinen, bei den Abschätzungen recht grob vorzugehen.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:13 Di 24.10.2006 | | Autor: | dump_0 |
Ich danke dir für deine Antwort.
Ja, mit log meinte ich den 2er-Logarithmus, sorry, hatte ich vergessen zu erwähnen.
Ich werds jetzt mal probieren, die Reihenfolge hab ichs chonmal, jetzt muss ichs nur noch beweisen, so wie du es gezeigt hast :)
Grüße
|
|
|
|
