Verschoben! asymptotische Schranke

21.10.2014, 11:48

0664jester

asymptotische Schranke

gegeben: $\begin{eqnarray*} n! = O(n^{n}) \end{eqnarray*}$

Um zu zeigen, dass f(n) $\begin{eqnarray*} \in \end{eqnarray*}$ O(g(n)) ist, muss man eine Schranke
$\begin{eqnarray*} n_{0} \end{eqnarray*}$ angeben und dann argumentieren, dass f(n) $\begin{eqnarray*} \leq \end{eqnarray*}$ für alle
n $\begin{eqnarray*} \leq n_{0} \end{eqnarray*}$ erfüllt ist.

Es kann durch den Grenzwert gezeigt werden:

$\begin{eqnarray*} \lim_{n \to \infty} \frac{n!}{n^{n} } = \lim_{n \to \infty} \frac{1}{n} \end{eqnarray*}$

Laut definition:
$\begin{eqnarray*} \lim_{n \to \infty} \frac{n!}{n^{n} } = K \end{eqnarray*}$

$\begin{eqnarray*} 0 \leq K < \infty: f(n) = O(g(n)) \end{eqnarray*}$

somit stimmt der Grenzwert.

Kann man das so stehen lassen? Ich bin mir nicht sicher, ob ich den limes so berechnen darf?

Gruß,
jester

21.10.2014, 16:20

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von 0664jester
$\begin{eqnarray*} \lim_{n \to \infty} \frac{n!}{n^{n} } = \lim_{n \to \infty} \frac{1}{n} \end{eqnarray*}$

Letztendlich stimmt diese Gleichung - mir fehlt da allerdings eine überzeugende Begründung deinerseits. Augenzwinkern