Addition von natürlichen Zahlen

Die Summe der natürlichen Zahlen von 1 bis zu einer Endzahl N zu berechnen, ist ein gewöhnliches, häufig anzutreffendes Problem. Betrachtet man das Beispiel, in welchem sich N auf 10 beläuft, so wäre die nächst liegendste Idee, einfach die Zahlen einzeln aufzuaddieren, was 55 ergeben würde. Betrachtet man den Fall, N sei 357, stellt man schnell fest, daß die Addition der Zahlen ziemlich aufwendig ist.

Durch eine kleine C Funktion, welche manuell die Summe berechnet, ergibt sich ein lineares Verhalten für den Algorithmus, was für ein so häufiges Problem nicht akzeptabel ist.


\begin{listing}{1} int summe( int N ) { int i = 0; while( N ) i += N--; return (i); } \end{listing}

Um die Summe der Zahlen von 1 bis N zu berechnen, muss die obige Funktion N Durchläufe in ihrer Schleife durchführen. Somit würde diese Funktion in einem komplexerem Algorithmus einen Faktor N beitragen, was sehr schlechte Auswirkungen auf den Algorithmus haben kann.

Eine wesentlich ellegantere und effizientere Methode zur Berechnung der gewünschten Summe wurde schon 1786 von Karl Friedrich Gauß im Alter von 9 Jahren entdeckt und besitzt eine Komplexität von $O(1)$, sprich eine konstante Zeit. Dies wird durch eine Berechnung (Formel) erreicht, die moderne Maschinen in nur wenigen Taktzyklen erledigen können. Die hier vorgestellte Formel wird oft zur Analyse von Algorithmen benötigt, wie später ersichtlich wird, da sich häufig in Programmen die Situation ergibt, in der eine oder mehrere Operationen N mal durchgeführt werden müssen, die wiederum abhängig von N x mal wiederholt werden. Dank der Formel, können solche Problemstellen bei Algorithmen ersichtiglich gemacht und erkannt werden.

Die Idee sei hier erstmal an einem Beispiel, natürliche Zahlen bis zu 10 aufzuaddieren, vorgestellt. Der Clue liegt in der Vorgehensweise in der die Zahlen zusammen addiert werden. Diese beruht auf dem Kommutativgesetzt der Addition, da für die Addition gilt: $a + b = b + a$ Ebenso gilt für die Addition: $a + b + c = (a + b) + c = a + (b + c)$. Somit kann eine Reihe von Zahlen, die aufaddiert werden sollen, so umgeordnet werden, dass sich eine Regelmäßigkeit darin wiederspiegelt. Die folgende Abbildung soll dies verdeutlichen.


\begin{picture}(9,3.5) \psset{linecolor=gray} \psset{linewidth=.1pt} \put(0,3... ...line(0.2,2.8)(4.5,0.2) \psline(9.1,2.8)(4.9,0.2) \put(4.5,0){11} \end{picture}

Somit kann man die Reihe wie folgt berechnen:
$\times$

Angewandt auf ein Problem der Größe N lässt sich folgende Formel aufzeigen. Der einfachheitshalber soll zuerst die zweifache Summe errechnet werden, sprich die Problemgröße ist $2 \times N$.


$\times$

Da die Summe der natürlichen Zahlen zwischen 1 und N hier doppelt vorliegt, ist lediglich eine Division durch zwei durchzuführen .

\begin{displaymath}\frac{n \times (n + 1)}{2}\end{displaymath}

Die somit entstandene Formel zur Berechnung der Summe von natürlichen Zahlen zwischen 1 und N, kann durch einen arithmentischen Ausdruck in Rechnermaschinen in konstanter Zeit berechnet werden. Eine Komplexität von $O(1)$.

Nächste Seite  Aufwärts  Vorherige Seite  Inhalt 


Nächste Seite: Algorithmen Aufwärts: Aus der Mathematik Vorherige Seite: Aus der Mathematik   Inhalt

2002-05-09