0 Daumen
365 Aufrufe


Problem/Ansatz:

ich wollte wissen, ob O(log(n!)) = O(log(n^n)) gilt ? Und wenn nein, wieso ?

Avatar von

2 Antworten

0 Daumen
 
Beste Antwort

Hallo,

es gilt \(\log(n^n)=n\log(n)\). Das ist superlineares Wachstum, wie es bei vergleichsbasierten Algorithmen zum Sortieren von n Zahlen auftritt, z. B. Mergesort oder Heapsort.

Nach Stirlings Formel gilt:$$n!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$$ D. h. es gilt:$$\log(n!)\sim \log\left( \sqrt{2\pi n}\right)+n\cdot \log(n/e)$$ Im Wesentlichen also auch in \(\mathcal{O}(n\log(n))\).

Du siehst so, dass \(\lim\limits_{n\to\infty}\frac{\log(n^n)}{\log(n!)}=1\), was heißt, dass die beiden tatsächlich asymptotisch äquivalent sind.

Avatar von 28 k
0 Daumen

Hallo :-)

Man kann es auch so zeigen, indem ich folgende Defintion der Landau-Symbolik benutze:

Es sei \(g: \mathbb{N}\rightarrow \mathbb{R}\). Dann ist$$ \mathcal{O}(g):=\{f:\mathbb{N}\rightarrow \mathbb{R}:\exists \alpha>0 \ \exists n_{0} \in \mathbb{N} \ \forall n\in \N_{\geq n_0}:0\leq f(n) \leq \alpha \cdot g(n)  \} $$die Menge aller Funktion \(f\), die bis auf eine Konstante \(\alpha>0\) höchstens so schnell wächst wie \(g\).

Und jetzt dazu folgende Überlegung: Will man die Gleichheit \(\mathcal{O}(\log(n^n))=\mathcal{O}(\log(n!))\) zeigen, dann genügt es aufgrund der Transitivitätseigenschaften solcher Mengen nur die Spezialfälle zu zeigen, also:

$$ (i)\log(n!)\in\mathcal{O}(\log(n^n)) \\(ii) \log(n^n) \in\mathcal{O}(\log(n!))$$

Zu (i): Für alle \(n\in \N_{\geq 0}\) ist $$ 0\leq \log(n!)=\log(n\cdot (n-1)\cdot ... \cdot 2\cdot 1)=\sum\limits_{k=1}^n \log(k)\leq \sum\limits_{k=1}^n\log(n)=n\cdot \log(n)=\log(n^n) $$

Mit \(\alpha=1, n_0=0\) gilt also für alle \(n\in \N_{\geq 0}\) stets \(0\leq \log(n!)\leq \alpha\cdot \log(n^n)\), also folgt (i).


Zu (ii): Zeige induktiv für alle \(n\in \N_{\geq 2}\) die Abschätzung \(n^n\leq (n!)^2\).

Induktionsanfang: Für \(n=2\) ist \(2^2=4\leq 4=2^2=(2!)^2\).

Induktionsvoraussetzung: Angenommen, es gibt ein festes \(n\in \N_{\geq 2}\) mit \(n^n\leq (n!)^2\).

Induktionsschritt: Dann gilt auch \((n+1)^{n+1}\leq ((n+1)!)^2\). Dies folgt durch:

$$ ((n+1)!)^2=(n+1)^2\cdot (n!)^2\stackrel{(IV)}{\geq } (n+1)^2\cdot n^n=(n+1)^2\cdot \frac{(n+1)^{n+1}}{(n+1)^{n+1}}\cdot n^n\\=(n+1)^2\cdot (n+1)^{n+1}\cdot \frac{1}{n+1}\cdot \frac{n^n}{(n+1)^n}=(n+1)\cdot (n+1)^{n+1}\cdot \left(\frac{n}{n+1}\right)^n\\=(n+1)\cdot \left(\frac{n}{n+1}\right)^n\cdot (n+1)^{n+1}=(n+1)\cdot \frac{1}{\left(1+\frac{1}{n}\right)^n}\cdot (n+1)^{n+1}\\\stackrel{(*)}{\geq }(n+1)\cdot \frac{1}{3}\cdot (n+1)^{n+1}\stackrel{n\geq 2}{\geq} (2+1)\cdot \frac{1}{3}\cdot (n+1)^{n+1}=(n+1)^{n+1}$$

(*) Es gilt für alle \(n\in \N_{\geq 1}\) stets \(\left(1+\frac{1}{n}\right)^n\leq 3\).

Wegen Monotonie von \(\log(.)\) folgt also \(\log(n^n)\leq 2\cdot \log(n!)\).

Mit \(\alpha=2, n_0=2\) gilt also für alle \(n\in \N_{\geq 2}\) stets \(0\leq \log(n^n)\leq \alpha\cdot \log(n^n)\), also folgt (iI).

Avatar von 15 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community