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

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

On se pose la question suivante : combien faut-il de multiplications et d'additions pour calculer l'image d'un nombre par un polynôme de degré n ?

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

1. Combien de multiplications faut il pour calculer \(x^2\) ?
   
   
2. Combien de multiplications faut il pour calculer \(x^3\) ?
   
   
3. Combien de multiplications faut il pour calculer \(x^4\) ?
   
   
4. Combien de multiplications faut il pour calculer \(x^5\) ?
   
   
5. Combien de multiplications faut il pour calculer \(x^n\) ?
   
   

   Soit :

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

addition : multiplication :


Soit :

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

addition : multiplication :


Soit :

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

addition : multiplication :

9. Émettre une conjecture sur le nombre d'addition nécessaire pour calculer un polynôme de degré n.



10. 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.


11. 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

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\).
12. Ecrire la forme de horner du polynome g :
$$\fonction{g}{\mathbb{R}}{\mathbb{R}}{x}{4x^2+2x+5}$$

13. Donner le nombre d'opérations (additions + multiplications confondus) pour calculer \(g(3)\) avec cette écriture.


14. Ecrire la forme de horner du polynome h :
$$\fonction{h}{\mathbb{R}}{\mathbb{R}}{x}{2x^3+4x^2+2x+5}$$

15. Donner le nombre d'opérations (additions + multiplications confondus) pour calculer \(h(5)\) avec cette écriture.


16. Emettre une conjecture sur le nombre d'opérations nécessaires pour calculer un polynôme de degré n avec la méthode de Horner.


17. On veut convertir un entier sur 32 bits (soit donc calculer l'image de 2 par un polynome de degré 32), on suppose qu'une opération (multplication ou addition prend une seconde), calculer le temps nécessaire avec la méthode classique puis avec la méthode de Horner.

Horner: Basique :

18. On veut caclculer l'image d'un entier par un polynôme de degré 64, on suppose qu'une opération (multplication ou addition prend une seconde), calculer le temps nécessaire avec la méthode classique puis avec la méthode de Horner.

Horner: Basique :