Vergleich von Aufwandsklassen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:57 Fr 18.11.2011 | | Autor: | MISTERX |
| Aufgabe | Sind diese Funktionen f(n) = 2*log(2n) und g(n) = [mm] 4*\wurzel{n} [/mm] in der gleichen oder in
unterschliedlichen Aufwandsklassen. Beweise deine Antwort! |
Hallo,
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich würde gerne wissen wie soetwas zu zeigen ist und wie man dabei vorgehen muss.
Muss man zunächst die Aufwandsklassen der Funktionen erraten und dann diese vergleichen?
Soweit habe ich folgendes:
f(n) [mm] \in [/mm] O(log(n)) und g(n)= [mm] O\wurzel{n} [/mm] (ist das auch zu zeigen?)
Behauptung: f(n) [mm] \in [/mm] g(n)
--> 2*log(2n) [mm] \le c*\wurzel{n})
[/mm]
--> [mm] \limes_{n\rightarrow\infty} \bruch {2*log(2n)}{\wurzel{n}}=0
[/mm]
(konvergiert gegen einen Grenzwert)
--> somit ist die Behauptung korrekt, und f(n) und g(n) sind in der gleichen Aufwandsklasse.
Stimmt das so? Aber irgendwie ist das ja kein Beweis.
Ich hoffe ihr könnt mir hierbei weiterhelfen.
Vielen Dank im Voraus
Gruß,
MisterX
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:07 Fr 18.11.2011 | | Autor: | felixf |
Moin!
> Sind diese Funktionen f(n) = 2*log(2n) und g(n) =
> [mm]4*\wurzel{n}[/mm] in der gleichen oder in
> unterschliedlichen Aufwandsklassen. Beweise deine
> Antwort!
>
> Ich würde gerne wissen wie soetwas zu zeigen ist und wie
> man dabei vorgehen muss.
> Muss man zunächst die Aufwandsklassen der Funktionen
> erraten und dann diese vergleichen?
Nicht umbedingt.
> Soweit habe ich folgendes:
> f(n) [mm]\in[/mm] O(log(n)) und g(n)= [mm]O\wurzel{n}[/mm] (ist das auch zu
> zeigen?)
Ja, das hast du. Im Zweifelsfall wuerde ich es kurz zeigen; mit ein paar Rechenregeln zum Landau-Symbol geht das schnell.
> Behauptung: f(n) [mm]\in[/mm] g(n)
Du meinst: $f(n) [mm] \in [/mm] O(g(n))$ (oder wie man manchmal schreibt, $f(n) = O(g(n))$)
> --> 2*log(2n) [mm]\le c*\wurzel{n})[/mm]
> -->
> [mm]\limes_{n\rightarrow\infty} \bruch {2*log(2n)}{\wurzel{n}}=0[/mm]
>
> (konvergiert gegen einen Grenzwert)
> --> somit ist die Behauptung korrekt, und f(n) und g(n)
> sind in der gleichen Aufwandsklasse.
Nein, du hast nur gezeigt: $f(n) [mm] \in [/mm] O(g(n))$.
Du muesstest jetzt noch zeigen $g(n) [mm] \in [/mm] O(f(n))$ um zu zeigen, dass sie wirklich in der gleichen Aufwandsklasse liegen.
Dazu musst du dann [mm] $\lim_{n\to\infty} \frac{\sqrt{n}}{2 \log(2 n)}$ [/mm] betrachten. Und wie du vielleicht schon sehen kannst: das geht gegen unendlich, da der Grenzwert von der Kehrbruchfolge 0 ist (wie du oben bestimmt hast).
Du kannst dir auch allgemeiner ueberlegen: $f$ und $g$ gehoeren genau dann zur gleichen Aufwandsklasse, falls [mm] $\lim_{n\to\infty} \frac{f(n)}{g(n)}$ [/mm] gegen eine Zahl in $(0, [mm] \infty)$ [/mm] konvergiert (womit 0 und [mm] $\infty [/mm] $ausgeschlossen sind!).
[Es kann natuerlich noch vorkommen, dass der Grenzwert nicht existiert. In dem Fall ist die Bedingung, dass $f$ und $g$ in der gleichen Aufwandsklasse liegen, aequivalent zu $0 < [mm] \liminf_{n\to\infty} \frac{f(n)}{g(n)}$ [/mm] und [mm] $\limsup_{n\to\infty} \frac{f(n)}{g(n)} [/mm] < [mm] \infty$.]
[/mm]
LG Felix
|
|
|
|
