M&A Somme des premiers entiers

Section 3.1 Somme des premiers entiers

Comment utiliser efficacement l'ordinateur pour calculer la somme des \(n\) premiers entiers non nuls

\begin{equation*} \sum_{k=1}^nk=1+2+\cdots+n\;? \end{equation*}

Combien d'additions doit-on effectuer pour évaluer la somme

\begin{equation*} \sum_{k=1}^{5}k=1+2+3+4+5\;? \end{equation*}

Il en faut quatre. Plus généralement, on a besoin de \(n-1\) additions pour évaluer la somme des \(n\) premiers entiers naturels non nuls

\begin{equation*} \sum_{k=1}^nk=1+2+3+\cdots+n. \end{equation*}

Voici une implémentation de l'algorithme qui renvoie la valeur de cette somme en suivant cette approche naïve.

Pour faire simple, on peut considérer que la vitesse d'exécution de cet algorithme dépend essentiellement du nombre d'additions qu'il doit effectuer.

Notons \(T(n)\) ce nombre qui dépend de l'entier donné en entrée comme suit :

\begin{equation*} T(n)=n-1. \end{equation*}

La fonction \(T\) ainsi définie est une estimation de la complexité en temps de cet algorithme.

Plus \(n\) est grand, plus le temps de calcul représenté par \(T(n)\) est grand.

Comme \(T\) dépend linéairement de \(n\text{,}\) on dit que la complexité de cet algorithme est linéaire.

En fait, il existe une formule bien connue qui permet de calculer directement la valeur de \(\displaystyle\sum_{k=1}^nk\text{.}\) La voici :

\begin{equation*} \sum_{k=1}^nk=\frac{n(n+1)}{2}. \end{equation*}

Quelle que soit la valeur de \(n\text{,}\) cette approche ne requiert que trois opérations : une multiplication, une addition et une division.

Autrement dit, l'algorithme

a une complexité en temps constante

\begin{equation*} T(n)=3. \end{equation*}

Il s'agit donc d'un algorithme beaucoup plus efficace que le précédent pour résoudre le problème 3.1.1.