示例2:乘法 乘法公式 6x3+7x2-10x+9 C(x)=A(x)BO 30x3-35×2+50X-45 24×4+28x3-40x2+36x 12x6-14x5+20x4-18x3 ab-k,j=0.…2n-2 12x6-14x5+44x4-20x3-75x2+86X-45 多项式表示法 系数表示法宜于求值和加法 算A()在点X0的值A(x Horners rule方法计算时间复杂度(mn =ao+x0(a,+X0(a2+…+X0(an2+X0an)…) 加法就是向量相加 a=(a0,a1,an.可以用一个n维向量来表示 而对于乘法 点值表示法 对于由系数表示的多项式A(x)和B(x),其 点值表示( point-value representation) 乘法复杂度是0(n2 幂次为n-1的多项式A(x)可以由点值对 其积的系数向量c,被称为是a和b的卷积 point-value pairs convolution并记做c=at f(xoyb),(x1,yb,,(xn3yn)来表示 由于多项式乘法和卷积运算都是基本运 其中xk互不相等,yk=A(X) 算,我们重点来计算卷积的高效率算法2 示例2：乘法 • 6x3 + 7x2 - 10x + 9 • - 2x3 + 4x - 5 • ------------------------------------------------------------ • - 30x3 - 35x2 + 50x - 45 • 24x4 + 28x3 - 40x2 + 36x • - 12x6 - 14x5 + 20x4 - 18x3 • ------------------------------------------------------------ • - 12x6 - 14x5 + 44x4 - 20x3 - 75x2 + 86x - 45 乘法公式 C(x) = A(x)B(x) , 0,...,2 2 1 0 =∑ = − − = c a b − j n n k j k j k 多项式表示法 • a = (a0, a1, . . ., an-1). 可以用一个n维向量来表示。 ∑ − = = 1 0 ( ) n j j j A x a x 系数表示法宜于求值和加法 • 计算 A(x) 在点 x0 的值 A(x0). • Horner‘s rule方法计算时间复杂度 θ (n) : • A(x0) = a0 + x0(a1+x0(a2+ ... +x0(an-2+x0(an-1))...)). • 加法就是向量相加 而对于乘法 • 对于由系数表示的多项式 A(x) 和 B(x) ，其 乘法复杂度是 θ (n2), • 其积的系数向量 c, 被称为是a和b的卷积 convolution 并记做 c = a*b. • 由于多项式乘法和卷积运算都是基本运 算，我们重点来计算卷积的高效率算法 点值表示法 • 点值表示（ point-value representation） 幂次为n-1的多项式 A(x) 可以由点值对 （ point-value pairs ） • {(x0, y0), (x1, y1), . . ., (xn-1, yn-1)} 来表示 • 其中 xk 互不相等，yk = A(xk)