Soient
et
deux polynô
eur produit.
Ils sont représentés par {a=[|a_{0};a_{1};...;a_{m}|],b=[|b_{0};b_{1};...;b_{n}|]} et {c=[|c_{0};c_{1};...;c_{m+n}\quad |].}
8.3.1 Algorithme naïf
On voit ici une fonction de multiplication na ̈ive de deux polynômes {A} et {B.} Tout le travail est fait dans la double boucle (on ne considère pas ici le coût de la création du tableau {c} en mémoire, et de son initialisation à 0) :
|
1 2 3 4 5 6 7 8 9 10 11 |
let mul_pol_array a b = let m = Array.length a - 1 (* on a deg(A) <= m *) and n = Array.length b - 1 (* on a deg(B) <= n *) in let c = Array.make (m+n+1) 0. in (* donc deg(C = AB) <= m + n *) for i = 0 to m do (* pour chacun des coeffs de A *) for j = 0 to n do (* et pour chacun des coeffs de B *) c.(i+j) <- c.(i+j) +. a.(i)*.b.(j) (* actualise coef de X i+j dans C = AB *) done; done; c;; val mul_pol_array : float array -> float array -> float array = <fun> |
Il y a {2mn} opérations élémentaires (autant d’additions que de multiplications). Pour multiplier deux polynômes de {\mathbb{K}_{n-1}\quad [X],} il faut donc prévoir {2n^{2}} opérations élémentaires.
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres