Introduction à la complexité d'un algorithme : Méthode de Horner

Nombres d'opérations nécessaires pour effectuer le calcul d'une image par la méthode classique.

Combien faut-il de multiplications et d'addition pour calculer l'image d'un nombre par un polynôme ?

Pour calculer la puissance n d'un nombre nous utiliserons la méthode basique :$$x^n=\underbrace{x×x×x×\ldots×x}_{n fois}$$

Soit :

$$\fonction{f}{\mathbb{R}}{\mathbb{R}}{x}{2x+5}$$
1. Combien faut-il de effectuer de multplications puis d'additions pour déterminer \(f(2)\) ?

Soit :

$$\fonction{g}{\mathbb{R}}{\mathbb{R}}{x}{4x^2+2x+5}$$
2. Combien faut-il de effectuer de multplications puis d'additions pour déterminer \(g(3)\) ?

Soit :

$$\fonction{h}{\mathbb{R}}{\mathbb{R}}{x}{2x^3+4x^2+2x+5}$$
3. Combien faut-il de effectuer de multplications puis d'additions pour déterminer \(h(5)\) ?
4. Emetre une conjecture sur le nombre d'addition nécessaire pour calculer un polynome de degré n.
5. Compléter en mettant le nombre de multiplications nécessaire au calcul :
$$\underbrace{a_nx^n}_{\ldots}+\underbrace{a_{n-1}x^{n-1}}_{\ldots}+\underbrace{a_{n-2}x^{n-2}}_{\ldots}+\ldots+\underbrace{a_3x^{3}}_{\ldots}+\underbrace{a_2x^{2}}_{\ldots}+\underbrace{a_1x}_{\ldots}+\underbrace{a_0}_{\ldots}$$
Remarque
On montre en mathématiques que \(n+(n-1)+(n-2)+\ldots+3+2+1 = \frac{n(n+1)}{2}\)
Vous pouvez regarder les figures suivantes pour avoir une idée pour une méthode graphique de démonstration.


6. En deduire le nombre d'opérations (multiplications et additions confondus) nécessaire au calcul d'une image par une fonction polynôme de degré n.

Méthode de Horner.

Le mathématicien anglais William George Horner (1786-1837) a proposé une autre manière de calculer l'image d'un nombre par une fonction polynôme.



Pour calculer l'image d'un nombre x par la fonction polynôme f(x)=\(a_nx^n+a_{n-1}x^{n-1}+...a_1x+a_0\) on utilise l'algorithme suivant :

\(a_n\),\(a_{n-1}\),...,\(a_0\) et x sont donnés.
rep=\(a_{n}\)
Pour i allant de n-1 à 0 en reculant de 1 à chaque fois :
rep=x×rep
rep=rep+\(a_i\)
On retourne rep
Remarque
L'idée dérrière l'algorithme est une écriture différente du polynôme par exemple :
• Si \(f(x) = 3x²+4x+2\) alors on écrit \(f(x) = x(x×(3)+4)+2\).
• Si \(g(x) = 4x^3+3x^2+2x+1\) alors on écrit \(g(x)=x(x(x×4+3)+2)+1\).
7. Donner les différentes valeurs de rep de l'algorithme si on souhaite calculer g(3) avec :
$$\fonction{g}{\mathbb{R}}{\mathbb{R}}{x}{4x^2+2x+5}$$
8. Donner le nombre d'opérations (additions + multiplications confondus) nécessaire au calcul de l'image d'un nombre par une fonction polynôme de degré n.
9. Compléter le tableau suivant :

degré du polynôme	Nombre d'opérations méthode 1	Nombre d'opérations méthode 2	Rapport :\(\frac{Nombre\: d'opérations\: méthode\: 1}{Nombre\: d'opérations\: méthode\: 2}\)
1
8
32