Asymptotische Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:16 Mo 13.02.2006 | | Autor: | nevinpol |
| Aufgabe | Bestimmen Sie für die folgenden Paare, ob $f=O(g)$, [mm] $f=\Omega(g)$, [/mm] $f=o(g)$, [mm] $f=\omega(g)$ [/mm] oder keine dieser Relationen gilt.
1. [mm] $f(n)=log_{2} [/mm] n$ und [mm] $g(n)=log_{10} [/mm] n$
2. [mm] $f(n)=\bruch{n}{log_{100} n}$ [/mm] und [mm] $g(n)=\wurzel{n}$
[/mm]
3. [mm] $f(n)=50\cdot n^2$ [/mm] und [mm] $g(n)=(75-50\cdot(n \mod 2))\cdot n^2$
[/mm]
4. [mm] $f(n)=n^3+3n^2$ [/mm] und [mm] $g(n)=\begin{cases} 4n^4, & \mbox{für } n \mbox{ gerade} \\ 2n^2, & \mbox{für } n \mbox{ ungerade} \end{cases}$
[/mm]
|
Ich habe folgende Lösungen vom Tutorium aber ich habe sie nicht verstanden. Z.B. bekomme ich bei der 1. unendlich raus, wenn ich den Limes berechne, aber wie kommt der Tutor drauf, dass es sowohl $f=O(g)$, [mm] $f=\Omega(g)$ [/mm] als auch [mm] $f=\Theta(g)$ [/mm] ist. Hier sind die Lösungen vom Tut:
1. $f=O(g)$ und [mm] $f=\Omega(g)$ [/mm] und [mm] $f=\Theta(g)$
[/mm]
2. $f=O(g)$
3. $f=O(g)$ und [mm] $f=\Omega(g)$ [/mm] und [mm] $f=\Theta(g)$
[/mm]
4. keine der Relationen gilt
Wie muss ich überhaupt vorgehen? Ich sitze schon seit Stunden an der ersten und komme auf ganz viele verschiedene Ergebnisse. Wie kann ich das überhaupt aufschreiben als Lösung.
Vielen Dank für Euer Zeit
Grüße
nevinpol
|
|
| |
|
Guten Morgen,
also vorab wuerd ich mir die Definitionen mal hinschreiben, dann sieht man schon mal, was ueberhaupt zu untersuchen ist.
Also es gilt ja per definitionem
f=O(g) [mm] \:\Leftrightarrow\: \exists c>0,\: n_0>0\:\forall n\geq n_0 f(n)\leq c\cdot g(n)\:\Leftrightarrow \lim\sup_{n\to\infty}\frac{f(n)}{g(n)}\:\: <\infty
[/mm]
Zur ersten: [mm] f(n)=\log_a(n), g(n)=\log_b(n)=\frac{\log_a(n)}{\log_a(b)} [/mm] fuer a<b, diese wunderbare 
Rechenregel fuer Logarithmen hilft hier schon mal komplett weiter, zB ist ja
[mm] f(n)\leq c\cdot [/mm] g(n)
fuer [mm] c=\frac{1}{\log_a(b)} [/mm] (waehle so, dass a<b).
Ganz allgemein folgt ja aus [mm] f(n)=c\cdot [/mm] g(n) fuer eine Konstante c und alle n, dass [mm] f=\Theta [/mm] (g).
Noch zur zweiten: Es ist [mm] f(n)=c\cdot \frac{n}{\log (n)} [/mm] (Logarithm. zur Basis 2, von mir aus), und [mm] g(n)=\sqrt{n}.
[/mm]
Dann gilt
[mm] \frac{f(n)}{g(n)}=c\cdot \sqrt{n}\cdot\log [/mm] (n), und dies divergiert gegen [mm] \infty, [/mm] was also zeigt: [mm] f(n)=\Omega [/mm] (g(n)), sogar
[mm] f(n)=\omega [/mm] (g(n)) und g(n)=o(f(n)), insbesondere also g(n)=O(f(n)), [mm] f(n)\neq [/mm] O(g(n)).
Kommst Du jetzt schon mal weiter ?
Viele Gruesse,
Mathias
|
|
|
|
