Komplexität von Funktionen

09.12.2006, 16:26

JayT

Komplexität von Funktionen

Hallo!

Ich soll mittels der Landau-Notation folgende Abschätzungen zeigen:

a) $\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$ gleich Theta( $\begin{eqnarray*} n^{k} \end{eqnarray*}$ ), für alle $\begin{eqnarray*} k\in \mathbb N \end{eqnarray*}$
b) $\begin{eqnarray*} \sum_{i=1}^n~i^{k} \end{eqnarray*}$ gleich Theta( $\begin{eqnarray*} n^{k+1} \end{eqnarray*}$ ) für alle $\begin{eqnarray*} k\in \mathbb N \end{eqnarray*}$

Für den Binomialkoeffzienten dachte ich mir, dass $\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} = \frac{n(n-1)(n-2)...1}{(n-k)! k!} \leq \frac{n*n*n...*n}{(n-k)! k!}=\frac{n^{n}}{(n-k)! k!} = \frac{n^{n-k}}{(n-k)!} \end{eqnarray*}$ . Dies scheint mir zum Ziel führen zu können, jedoch weiß ich nach diesem Schritt nicht weiter! Könnte mir bitte jemand helfe?

Für Aufgabenteil b) habe ich leider noch gar keine Ahnung, wie ich vorgehen soll. Für einen Tipp wäre ich sehr dankbar!

MfG

Jay

09.12.2006, 16:42

sqrt(2)

Auf diesen Beitrag antworten »

RE: Komplexität von Funktionen
Ich nehme an, ihr habt etwa dieses gezeigt:

$\begin{eqnarray*} f(n)=\theta(g(n))~\Lra~\lim_{n\to\infty}\frac{f(n)}{g(n)}=0 \end{eqnarray*}$

Zitat:

Original von JayT
Für den Binomialkoeffzienten dachte ich mir, dass $\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} = \frac{n(n-1)(n-2)...1}{(n-k)! k!} \leq \frac{n*n*n...*n}{(n-k)! k!}=\frac{n^{n}}{(n-k)! k!} = \frac{n^{n-k}}{(n-k)!} \end{eqnarray*}$

Die letzten zwei Gleichheitszeichen sind falsch. Da sollte stehen

$\begin{eqnarray*} ...=\frac{n^k}{k!(n-k)!}\leq n^k \end{eqnarray*}$ .

Damit ist es einfach zu zeigen, dass obige Bedingung gilt.

09.12.2006, 16:52

JayT

Auf diesen Beitrag antworten »

Erst einmal vielen Dank für die schnelle antwort!

Zitat:

Original von sqrt(2)

$\begin{eqnarray*} f(n)=\theta(g(n))~\Lra~\lim_{n\to\infty}\frac{f(n)}{g(n)}=0 \end{eqnarray*}$

leider haben wir das nicht gezeigt.

Zitat:

Original von sqrt(2)
Die letzten zwei Gleichheitszeichen sind falsch. Da sollte stehen

$\begin{eqnarray*} ...=\frac{n^k}{k!(n-k)!}\leq n^k \end{eqnarray*}$ .

Damit ist es einfach zu zeigen, dass obige Bedingung gilt.

und ich verstehe nicht ganz, warum das gilt. könntest du ne kurze erklärung dazu geben?

09.12.2006, 17:06

sqrt(2)

Auf diesen Beitrag antworten »

Zitat:

Original von JayT
leider haben wir das nicht gezeigt.

Wie habt ihr die Laudau-Symbole definiert?

Zitat:

Original von JayT
und ich verstehe nicht ganz, warum das gilt. könntest du ne kurze erklärung dazu geben?

Wenn du "das" spezifizierst...

09.12.2006, 17:24

JayT

Auf diesen Beitrag antworten »

RE: Komplexität von Funktionen
Wir haben die Landausymbole (hier: Theta) so definiert:

$\begin{eqnarray*} \theta(g(n)) = \{ f(n): \exists C_1,C_2 > 0, \exists n_0\in \mathbb N _0: C_1\mid g(n) \mid \leq \mid f(n) \mid\leq C_2\mid g(n) \mid \forall n>n_0\} \end{eqnarray*}$

und was ich nicht verstehe, ist:

Zitat:

Original von sqrt(2)
Die letzten zwei Gleichheitszeichen sind falsch. Da sollte stehen

$\begin{eqnarray*} ...=\frac{n^k}{k!(n-k)!}\leq n^k \end{eqnarray*}$ .

Vielen Dank für die Hilfe!

09.12.2006, 18:05

sqrt(2)

Auf diesen Beitrag antworten »

Hm, ich hab dein Landausymbol schon einmal für ein anderes gehalten, und einen Copy-and-Paste-Fehler in der Gleichungskette.

Man kann schreiben

$\begin{eqnarray*} {n\choose k}=\frac{n(n-1)(n-2)\cdots(n-k+1)}{k!} \end{eqnarray*}$ .

D.h. es handelt sich um ein Polynom k. Grades. Ihr habt wahrscheinlich bewiesen, dass solche Polynome Elemente von $\begin{eqnarray*} \Theta(n^k) \end{eqnarray*}$ sind.

09.12.2006, 19:39

JayT

Auf diesen Beitrag antworten »

Danke schön!

Neue Frage »

Antworten »

Komplexität von Funktionen

Verwandte Themen