Binomialrekursion

In diesem Artikel geht es, in Ergänzung zu den Ausführungen über die Binomialformel, um die Ausnutzung der Binomialkoeffizientenrekursion zu einer (effizienteren) Berechnung der Koeffizienten.
Die Binomialkoeffizientenrekursion lautet:

Hier geht es nun darum, wie man mit Hilfe dieser Formel das Problem, alle Koeffizienten für ein festes n zu berechnen, (halbwegs) effizient lösen kann:
Betrachten wir zunächst den naiven Ansatz, für eine feste natürliche Zahl n alle Binomialkoeffizienten \(\displaystyle {n\choose k}, k=0,\ldots,n\) direkt zu berechnen, d.h. wir gehen nach folgendem Algorithmus vor:
Es sei n gegeben, zu berechnen sind die Binomialkoeffizienten, zur Abkürzung schreiben wir \[ b_{n,k} := {n \choose k} \]

• Für k = 0 bis n berechne
  • b_n,k = n! / (k! (n-k)!)

Dabei wird zunächst n! berechnet, und dann sind für jedes k die Werte k! und (n-k)! zu berechnen, d.h. wir haben als Aufwandsabschätzung: Die äußere Schleife wird n mal durchlaufen, für jedes k ist k! und (n-k)! zu berechnen, was im Wesentlichen n Multiplikationen sind, wir haben also einen Aufwand von O(n²), d.h. die Laufzeit wächst höchstens so schnell wie n².
Das ist nicht besonders gut, außerdem gibt es zu bemängeln, dass jedes mal große ganze Zahlen erst berechnet und dann dividiert werden, was (beim Rechnen mit Dezimalzahlen) zu Lasten der Genauigkeit bzw. (beim Rechnen mit ganzen Zahlen) zu Lasten der Rechenzeit geht.
Betrachte nun folgenden Ansatz, der alle Koeffizienten mit Hilfe der Rekursionsformel gleichzeitig berechnet, er hat zwar auch die Laufzeit O(n²), vermeidet aber die Division großer Zahlen, er verwendet nur Addition:

• Initialisiere alle b_n,k mit 1, d.h. im Falle n=0 sind wir fertig.
• Für k = 1 bis n tue (wir berechnen sukzessive eine neue Zeile des Pascalschen Dreiecks)
  • Setze c = 1 (zwischenspeichern)
  • Für j = 1 bis k-1 tue
    • Setze d = b_n,j
    • b_n,j = c + d (Rekursionsformel!)
    • Setze c = d

Dieser Algorithmus hat (zwei Schleifen mit O(n) Durchläufen) dieselbe Laufzeit wie der andere, aber wir vermeiden jegliche Multiplikation und Division und die Zwischenergebnisse sind allesamt kleiner als das Endergebnis.
Als Beispiel haben wir den zweiten Algorithmus hier in JavaSkript implementiert, es wird die Binomialformel für natürliches n und k berechnet (den Quellcode können Sie sich bei Interesse unten ansehen). Da die Binomialkoeffizienten sehr schnell sehr groß werden, ist die Eingabe auf dreistellige Zahlen begrenzt.

(		)

Für Interessierte hier der Quellcode zur Berechnung der Binomialkoeffizienten:

  b = new Array(n+1);
  for(i = 0; i <= n; i = i+1){
      b[i] = 1;
  }

  for(i = 0; i <= n; i = i+1){
      c = 1;
      for(j = 1; j < i; j = j+1){
         d = b[j];
         b[j] = c + d;
         c = d;
      };
  };