Beweise für Landau-Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:31 Do 12.05.2005 | | Autor: | MarcusS |
Hallo,
ich habe hier zwei Aufgaben zur Landau-Notation, die jeweils bewiesen werden sollen.
a) n! = [mm] o(n^n)
[/mm]
Mein Lösungsversuch:
g(n) [mm] \in [/mm] o(f(n)) haben wir definiert als:
[mm] \limes_{n\rightarrow\infty} [/mm] g(n)/f(n) = 0
Setz ich also für g = n! und für f = [mm] n^n [/mm] dann kriege ich:
[mm] \limes_{n\rightarrow\infty} n!/n^n [/mm] = 1
Damit aber wäre o(f(n)) widerlegt, denn [mm] \limes_{n\rightarrow\infty} [/mm] g(n)/f(n) = 1 sagt ja aus, dass g(n) [mm] \in [/mm] O(f(n))
Das versteh ich nun nicht so ganz :(
b) [mm] \summe_{k=0}^{n} \vektor{n \\ k}2^k [/mm] = [mm] \Theta(3^n)
[/mm]
Hier soll ich also beweisen, dass die Summe = [mm] 3^n [/mm] entspricht. Aber wie mache ich das korrekt? Per induktivem Beweis? Das wäre dann ja etwa so:
Base: n = 0
[mm] \summe_{k=0}^{0} \vektor{0 \\ 0}2^0 [/mm] = [mm] \Theta(3^0)
[/mm]
==> 1 = 1 ok
it step: n = n+1
[mm] \summe_{k=0}^{n+1} \vektor{n+1 \\ 0}2^0 [/mm] = [mm] \Theta(3^{n+1})
[/mm]
==> [mm] \summe_{k=0}^{0} \vektor{0 \\ 0}2^0 [/mm] + [mm] \vektor{1 \\ 0}2^0 [/mm] + [mm] \vektor{1 \\ 1}2^1= \Theta(3^{1}) [/mm] ok
Wär das die richtige Vorgehensweise oder sträuben sich da euch die Haare? Und wo liegt mein Fehler bei a)?
Danke & Grüße
Marcus
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> b) [mm]\sum_{k=0}^n{\binom{n}{k}2^k} = \Theta\left(3^n\right)[/mm]
Das ist ein Sonderfall des binomischen Lehrsatzes:
[mm]\sum_{k=0}^n{\binom{n}{k}2^k} = \sum_{k=0}^n{\binom{n}{k}1^{n-k}2^k} = (1+2)^n = 3^n = \Theta\left(3^n\right)[/mm]
Den Beweis für den binomischen Lehrsatz kann man ja in Büchern oder im Internet nachschlagen... (wenn man's nicht selber nochmal beweisen will.)
Gruß
Karl
|
|
|
| |
|
Hallo Marcus,
Die andere Aufgabe finde ich schon irgendwie schwer, aber die erste könnte man ja mal versuchen. n! ist eine harte Nuß mit der sich jedoch ein ![[]](/images/popup.gif) heller Geist schon vor ~ 300 Jahren beschäftigt hat. Wegen James Stirling sollte es uns also gelingen dieses Grenzwert-Problem zu knacken:
[m]\limes_{n\rightarrow\infty} {\frac{n!}{n^n}} \mathop = \limit^{\text{nach J. Stirling}} \limes_{n\rightarrow\infty} {\frac{\wurzel{2\pi n}\left(\frac{n}{e}\right)^n}{n^n}} = \limes_{n\rightarrow\infty} {\frac{\frac{n^n \wurzel{2\pi n}}{e^n}}{n^n}} = \limes_{n\rightarrow\infty}{\frac{\wurzel{2\pi n}}{e^n}} = \wurzel{2\pi}\limes_{n\rightarrow\infty}{\frac{\wurzel{n}}{e^n}} = 0[/m]. Daraus folgt die Behauptung. [mm] $\square$
[/mm]
(Hoffentlich habe ich jetzt damit keine Zirkelargumentation verursacht, da ich nicht weiß wie Stirling diese Formel hergeleitet hat.)
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:31 Do 12.05.2005 | | Autor: | Karl_Pech |
> Und wo liegt mein Fehler bei a)?
Ohne deinen Rechenweg zu kennen, ist diese Frage nicht lösbar.
Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:29 Do 12.05.2005 | | Autor: | MarcusS |
Danke für die Antwort zu a) :)
Die dargestellten zwei Zahlen waren übrigens mein Lösungsweg ;)
Grüße
Marcus
|
|
|
|
