算法分析与设计2005春.课件.第12讲.pdf

内容提要
•多项式的表示方式
多项式与FFT –系数
–值
•多项式的基本运算
清华大学
–加减乘除
宋斌恒
•运算的效率分析
• FFT思想与实现
多项式多项式加法
n −1 n −1
j j
A( x) = ∑ a j x B ( x) = ∑ b j x
j = 0 j = 0
•在代数域F上的变量为x的多项式 n −1
• n是幂次(degree)的上界,我们称k是上述多项 C ( x) = c x j
式的幂次,如果幂次最大的非零系数是a , ∑ j
k
j = 0
C=A+B 示例1
•若A(x) = 6x3 + 7x2 -10x + 9
• B(x) = -2x3+ 4x -5,
•则 C(x) = 4x3 + 7x2 -6x + 4.
c j = a j + bj for j = 0,...,n −1
1
示例2:乘法乘法公式
• 6x3 + 7x2 -10x + 9
•-2x3 + 4x -5
•------------------------------------------------------------ C(x) = A(x)B(x)
•-30x3 -35x2 + 50x - 45
• 24x4 + 28x3 -40x2 + 36x
•-12x6 -14x5 + 20x4 -18x3 n−1
•------------------------------------------------------------ c j = ∑akbj−k , j = 0,...,2n − 2
•-12x6 -14x5 + 44x4 -20x3 -75x2 + 86x - 45 k=0
多项式表示法系数表示法宜于求值和加法
n−1 •计算 A(x) 在点 x0 的值 A(x0).
A(x) = a x j • Horner‘s rule方法计算时间复杂度θ(n) :
∑ j • A(x )
j=0 0
= a0 + x0(a1+x0(a2+ ... +x0(an-2+x0(an-1))...)).
•加法就是向量相加
• a = (a0, a1, . . ., an-1). 可以用一个n维向量来表示。
而对于乘法点值表示法
•对于由系数表示的多项式 A(x) 和 B(x) ,其•点值表示( point-value representation)
乘法复杂度是θ(n2), 幂次为n-1的多项式 A(x) 可以由点值对
•其积的系数向量 c, 被称为是a和b的卷积( point-value pairs )
convolution 并记做 c = a*b. •{(x0, y0), (x1, y1), . . ., (xn-1, yn-1)} 来表示
•由于多项式乘法和卷积运算都是基本运•其中 xk 互不相等,yk = A(xk)
算,我们重点来计算卷积的高效率算法
2
进一步思路点表示定理
•一个问题可能有多种等价表示方法。而不•对于{(x0, y0), (x1, y1), . . ., (xn-1, yn-1)} 存在
同的表示方法对思考、解决问题