傅里叶变换(Fourier Transform)：小多项式乘法 给定： 最多n次的多项式p(x),q(x)的系数 目标：求它们的乘积r(x)=p(x)q(x)的系数 多项式的表示方式： p(x)=ao+ax+a2x2+a3x3+...+anxn 1. 多项式的系数ao,a1,,an 计算r(x)=p(x)q(x)需要0(n2) ck=∑=oabk-j 2. 务2玻毫雍整晶器的r,写下po.p以…pn】 计算r(x)=p(x)q(x)只需要0(n) 令m≥2n+1,计算r(xo),r(x1),…,r(xm)只需要写下 p(xo)q(xo),p(x1)q(x1),...,p(xm)q(xm) 17 傅里叶变换 (Fourier Transform)：多项式乘法 17 给定：最多n次的多项式� � , �(�)的系数 目标：求它们的乘积 � � = � � �(�)的系数 多项式的表示方式： � � = �! + �*� + �'�' + �,�, + ⋯ + �#�# 1. 多项式的系数�!, �*, … , �# – 计算� � = � � �(�)需要�(�&) – �' = ∑#*$ ' �#�'+# 2. 多项式插值：选定基点�#, �', … , �%，写下� �F , � �( , … , � �G ， 则多项式� � 是唯一确定的 – 计算� � = � � �(�)只需要�(�) – 令� ≥ 2� + 1，计算� �$ , � �% , … , � �9 只需要写下 � �$ � �$ , � �% � �% , … , � �9 � �9