Beweis - Fakultät größer Logarithmus

30.04.2010, 10:25

Strulle

Beweis - Fakultät größer Logarithmus

Meine Frage:
Hallo Board-Gemeinde,
ich muss um die Koplexität eines Algorithmus zu berechnen, beweisen, dass $\begin{eqnarray*} \lim_{n \to \infty } n! \end{eqnarray*}$ stärker anwächst ,als $\begin{eqnarray*} \lim_{n \to \infty } n log (n) \end{eqnarray*}$
außerdem soll muss ich beweisen, dass $\begin{eqnarray*} \lim_{n \to \infty } n! \end{eqnarray*}$ stärker anwächst als $\begin{eqnarray*} \lim_{n \to \infty } 3^{n} \end{eqnarray*}$
und das Ganze mathematisch.

Meine Ideen:
meine Idee war das mit der l'Hopital´schen Regel zu machen (also Ableitung Zähler / Ableitung Nenner), allerdings ist n! nur für natürliche Zahlen definiert, sodass keine Ableitung funktioniert. Mein Dozent hat mir außerdem den Tip gegeben, die Logarithmengesetze anzuwenden. Allerdings komm ich da absolut nicht weiter.

Ich hoffe Ihr könnt mir helfen?!

30.04.2010, 10:37

Strulle

Auf diesen Beitrag antworten »

Achso: die Funktion des Algorithmus lautet:
$\begin{eqnarray*} f(n)=3^{n}+8*n!+log(n^{n}) \end{eqnarray*}$

Aus der Vermutung, dass die Komplexität gegen n! geht, resultiert nach der l'Hopital´schen Regel:

$\begin{eqnarray*} \lim_{n \to \infty } \frac{3^{n} }{n!} + \frac{8*n!}{n!} + \frac{log(n^{n}) }{n!} \end{eqnarray*}$
und nach dem Kürzen:

$\begin{eqnarray*} \lim_{n \to \infty } \frac{3^{n} }{n!} + 8 + \frac{log(n^{n}) }{n!} \end{eqnarray*}$

...nun ist zu beweisen, dass das Ergebnis 8 ist.
und genau hier komm ich nicht weiter.

30.04.2010, 10:41

Evelyn89

Auf diesen Beitrag antworten »

ich weiß jetzt nicht wie das die informatiker machen, aber es gibt da auf jeden fall mehrere möglichkeiten.

du könntest den schnittpunkt bestimmen und zeigen, dass die folge von da an größer/kleiner ist.

bedenke, dass gilt: $\begin{eqnarray*} n\cdot ln(n)=ln(n^n) \end{eqnarray*}$

Du kannst den Limes vielleicht auch erstmal weglassen und versuchen per Induktion zu zeigen, dass n! schneller wächst.

Sind alles nur Ideen. Vielleicht bringt dich das ja weiter? Freude

30.04.2010, 10:48

klarsoweit

Auf diesen Beitrag antworten »

Was $\begin{eqnarray*} \frac{3^n}{n!} \end{eqnarray*}$ angeht, kannst du mit vollständiger Induktion zeigen, daß ab einem genügend großem n die Ungleichung $\begin{eqnarray*} 3^n \leq (n-1)! \end{eqnarray*}$ gilt.

30.04.2010, 10:52

Strulle

Auf diesen Beitrag antworten »

Hallo erstmal Danke für die schnelle Antwort.
Leider bin ich in Sachen (vollständige) Induktion nicht so bewandert, sodass ich nicht mal weiß, wo ich hier eine Induktion ansetzen sollte, geschweige denn wie ich anschießend weiter machen soll.
der Gleichheit dieser zwei Logarithmen bin ich mir durchaus bewusst, was mich allerdings zu keinem Ergebnis führt.

Zu sagen wäre vieleicht noch, dass der Logarithmus bei der gestellten Aufgabe die Basis 2 hat.
Im Vorraus schon mal vielen Dank für die Bemühungen.

30.04.2010, 11:21

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von Strulle
Leider bin ich in Sachen (vollständige) Induktion nicht so bewandert, sodass ich nicht mal weiß, wo ich hier eine Induktion ansetzen sollte

Genau beim Beweis der von mir genannten Ungleichung. Das sollte für jemanden, der an einer Hochschule ist, kein Problem sein.

Zitat:

Original von Strulle
geschweige denn wie ich anschießend weiter machen soll.

Dann kannst du das 3^n in $\begin{eqnarray*} 0 \leq \frac{3^n}{n!} \end{eqnarray*}$ nach oben durch (n-1)! abschätzen und dann mal n gegen unendlich laufen lassen.

02.05.2010, 19:35

Strulle

Auf diesen Beitrag antworten »

Schönen Guten abend.
Also den einen Teil $\begin{eqnarray*} (\frac{3^n}{n!}) \end{eqnarray*}$ konnte ich nun lösen.

1. Schritt:
für n=7
n! >= 3^n
7! >= 3^7
5040 >= 2187

2.Schritt
(n+1)! >= 3^(n+1)
--> (n+1)! = n! * (n+1)
--> 3^(n+1) = 3*3^n
--> (n+1) >= 3 (hier das zeichen für: für alle) n >= 2

Ich hoffe doch mal ganz stark, dass das nun als mathematischer Beweis gilt?!

nun hab ich nur noch das Problem mit dem Logarithmus.

Wie gesagt: Dieser Rechenregel bin ich mir bewuus, weiß aber nicht, wie mir das bei dieser aufgabe helfen soll...
$\begin{eqnarray*} n\cdot ln(n)=ln(n^n) \end{eqnarray*}$

ich hoffe hier kann nochmal jemand mit dem zaunspfahl winken...

Schon mal vielen dank im vorraus

02.05.2010, 20:33

Strulle

Auf diesen Beitrag antworten »

okay neuer ansatz....
Langsam komm ich allerdings vor lauter zahlen durcheinander...

es wäre ja einfacher, nun zu beweisen, dass

(n+1)*log(n+1) < 3^n

da hier keine Fakultät mehr auftaucht...
hier habe ich allerdings das selbe problem: wo ist der hebel anzusetzen?

So?
log (n+1) log (log(n+1)) < n*log3

ich weiß nicht weiter....

02.05.2010, 23:40

gonnabphd

Auf diesen Beitrag antworten »

$\begin{eqnarray*} log(x) \leq x \Rightarrow log(n^n) \leq n^2 \end{eqnarray*}$

Die Abschätzung ist recht grob, solltest du auch selbst beweisen können.

Wink

*Zaunpfahl nun wegleg*

Neue Frage »

Antworten »

Beweis - Fakultät größer Logarithmus

Verwandte Themen