Theta einer Funktion? < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:24 Mi 04.04.2012 | | Autor: | bandchef |
| Aufgabe | Beweisen oder widerlegen sie:
[mm] $\underbrace{log(3n!)}_{=g(n)} [/mm] = [mm] \Theta(\underbrace{n \cdot log(n)}_{=f(n)})$
[/mm]
Hinweis benutzen sie für $n [mm] \to \infty: [/mm] n!$ die Stirlingformel. |
Die Definition von [mm] $\Theta$ [/mm] lautet ja: [mm] $\Theta(f(n)) [/mm] = [mm] \{g(n) | g(n) \in O(f(n)) \wedge g(n) \in \Omega(f(n)) \}$
[/mm]
Ich hab jetzt im ersten Schritt erstmal das n! durch die Stirlingformel ersetzt:
[mm] $\Rightarrow log\left(3 \cdot \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n \right) [/mm] = [mm] \Theta \left(n \cdot log(n) \right)$
[/mm]
Wie geht es nun an dieser Stelle weiter? Wenn das "groß O" betrachten sollte, würde ich wissen was zu tun ist. Da muss ich dann gegenüber einem c abschätzen mit [mm] $\lim_{n \to \infty} \frac{g(n)}{f(n)}. [/mm] Was aber nun beim [mm] $\Theta$ [/mm] zu tun ist weiß ich nicht und verstehe ich auch nicht wenn ich mir die Definition durchlese.
Könnt ihr mir da weiterhelfen?
|
|
| |
|
Hiho,
> [mm]\underbrace{log(3n!)}_{=g(n)} = \Theta(\underbrace{n \cdot
log(n)}_{=f(n)})[/mm]
Wie Marcel schon in einem anderen Thread schrieb, ist das Gleichheitszeichen hier unangebracht, du hast bisher auch immer richtigerweise [mm] \in [/mm] verwendet.
Warum jetzt nicht mehr?
> Was aber nun beim [mm]$\Theta$[/mm] zu tun ist weiß ich nicht und
> verstehe ich auch nicht wenn ich mir die Definition
> durchlese.
Die Definition sagt einfach, dass sowohl
$g(n) [mm] \in [/mm] O(f(n))$ als auch(!) $g(n) [mm] \in \Omega(f(n))$ [/mm] gelten muss, d.h. du musst beides zeigen.
Wenn du $g(n) [mm] \in [/mm] O(f(n))$ zeigen kannst, hast du schon mal die halbe Miete, fehlt dann nur noch $g(n) [mm] \in \Omega(f(n))$.
[/mm]
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:49 Mi 04.04.2012 | | Autor: | bandchef |
Das $=$ steht sogar auf meiner Angabe...
Ich zeige nun erstmal, dass $O(f(n))$ gilt (die Definition von O erspare ich mir jetzt mal!):
[mm] $\Rightarrow \lim_{n \to \infty} \frac{g(n)}{f(n)} \leq [/mm] c [mm] \Leftrightarrow \lim_{n \to \infty} \frac{log\left(3 \cdot \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n \right)}{n \cdot log(n)} \leq [/mm] c [mm] \Leftrightarrow [/mm] ...$
Hier wird's jetzt schon schwierig das riesige Teil so weiter zu vereinfach, dass man den limes laufen lassen kann. Hast du da evtl. eine Anregung für mich?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:24 Mi 04.04.2012 | | Autor: | leduart |
Hallo zerleg den oberen log erst mal in ne summe von log, dann zieh noch die Exponenten raus wie etwa [mm] log\wurzel{n}=1/2*logn [/mm] usw. aber warum du erst fragst und nicht mal losrechnest ist mir schleierhaft. Bist du forensüchtig?
gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:57 Mi 04.04.2012 | | Autor: | bandchef |
Ich hab jetzt mal so aufgelöst:
[mm] $\lim_{n \to \infty} \frac{log(3) + 0,5 log(2 \pi) + 0,5 log(n) + n \cdot log(n) - n \cdot log(e)}{n \cdot log(n)} \leq [/mm] c [mm] \Leftrightarrow [/mm] ...$
Stimmt das soweit? Was man sehen kann, ist, dass es nun log() gibt, die unabhängig von "n" sind. Die anderen haben alle irgendwie n mit drin... Wie's da aber nun weiter geht weiß ich echt nicht mehr...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:33 Mi 04.04.2012 | | Autor: | leduart |
Hallo
jetz schreib unter jeden Summanden den nenner, kürz soweit es geht und sie dir die einzelnen GW an!
Wieder: warum machst du das nicht von alleine?
Gruss leduart
|
|
|
|
