Aufgabe (Binomialkoeffizient) Informatik:

Question

Hey Leute,

ich und meine Übungspartner sind total Ratlos. Es geht um folgende Frage:

In der Voerlesung wurde der Rechenaufwand für die rekursive Berechnung der Fibonaccizahlen ermittelt. Versuchen Sie nun einen Ausdruck A_n,k zur Beschreibung der Komplexität der rekursiven Berechnung des Binomialkoeffizienten zu finden.

Formel zur Berechnung des Binomialkoeffizienten.
B_n,k = (n über k) = n! / (k!(n-k)!)
Weiterhin gilt B_n,0 = B_n,n = 1 für n größer gleich 0
Sowie B_n,k = B_n-1,k-1 + B_n-1,k für 0 < k < n

Morgen ist bereits schon die Abgabe, daher wäre eine Lösung super, damit man das Ganze wenigstens nachvollziehen kann.

Viele Grüße

Answer 1

Ich hoffe, dass Du die Abgabe noch erfolgreich fertigstellen konntest! Die folgende (Java) Funktion berechnet den Binomialkoeffizient rekursiv:

 public static int binom(final int n, final int k) {
     if (n == k || k == 0) {
     return 1;
     }
     return binom(n - 1, k) + binom(n - 1, k - 1);
 }

Es ist 

\(B_{n,k}=\begin{cases}1,&n=k\vee k=0\\B_{n-1,k-1}+B_{n-1,k}, \mathrm{sonst}\end{cases}\)

die rekursive Definition des Binomialkoeffizienten. Die dazugehörige Rekurrenzgleichung lautet:

\(T(n,k) = T(n-1,k) + T(n-1,k-1) + \mathcal{O}(1) \) mit \(T(n,n) = T(n,0) = \mathcal{O}(1)\)

Daraus folgt:

\(T(n) = \mathcal{O}(2^n)\)