第1页 / 共29页
第2页 / 共29页
第3页 / 共29页
第4页 / 共29页
第5页 / 共29页
第6页 / 共29页
第7页 / 共29页
第8页 / 共29页
多项式乘法快速算法FFT.ppt
张家琳
复旦大学附属中学
引言
多项式是最基本的数学工具之一，由于其形式简单，且易于
用计算机对其进行各种计算，在当今的社会中应用越来越广。不
仅在像Maple这样的数学软件中有着举足轻重的作用，在工程、
信息等诸多领域中都有着广阔的应用。
下面我们给出几个多项式逼近的例子：
ln(
x
1)
x
sin
x
x
3
x
3!
2
x
2
5
x
5!
3
x
3
7
x
7!
c o s
x
1
2
x
2 !
4
x
4 !
6
x
6 !
( 1)
n
2
n
x
( 2 ) !
n
4
x
4
( 1)
n
1
n
x
n
( 1)
n
2
x
(2
n
n
1
1)!
多项式的基本运算
加法运算
求值运算
( )
f x
a
0
a
0
乘法运算
2
a x
a x
1
2
*(
*(
x a x a
2
1
n
a x
n
*(
x a
1
n
* )
x a
n
))
普通的多项式乘法运算
多项式乘法是一个很常见的问题，在通常
n
2(
)
O n
的算法中，两个 次多项式的乘法需要用
的时间才能完成。
让我们先来看一看这样的算法是如何进行的：
n
a x
n
b x
n
n
a x
1
n
x
b
1
n
n
1
n
1
...
...
a x a
1
0
b x
1
b
0
n
a b x
0
n
b x
a
1 1
n
1
n
a b x
1 0
n
...
...
2
a b x
1 1
n
ab x a b
1 0
0 0
a b x
1 0
*
a b x
1
n
n
1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
a b x
n
n
2
n
...
a b x
1
n
n
1
a b x
0
n
n
a b x
n n
2
n
......
n
k
1
a
n
1
k
b x
k
n
1
n
k
0
a
n k
n
b x
k
...
(
a b
1 0
a b x a b
0 1
0 0
)
在上面的过程中，似乎我们觉得这个算法并没有做任何多
余的事情，因为我们必须考虑每一组 ,它们的乘积对最终
的结果都会产生影响。而且我们不能通过调整计算顺序从根本
上降低算法时间复杂度，至多只能使其常数因子稍小一些。
a b
i
j
如果我们不能跳出以上思维的局限，我们就不可能在根本
上降低算法的时间复杂度。
让我们首先换一个角度来考察多项式。
多项式的点值表示法
首先让我们来看多项式的另一种表示方法：点值表示法,
(
f x
即用 （其中， 互不
i
相同）来表示一个不超过 次多项式。
),( ,
x y
1
1
),......,(
(
,
x y
0
0
),(
x y
2, 2
,
y x
i
i
)
,
x
y
1
1
n
n
1n
)
给定一个多项式，要给出n组点值对最简单的方法是任
选 n个互不相同的xi，依次求出多项式在这n个点的值。
用n个点值对也可以唯一确定一个不超过n-1次多项式，
这个过程称之为插值。
引理1（多项式插值的唯一性）
),(
,
x y
1
1
对于任意n个点值对组成的集合,
,
{(
x y
其中 互不
0
0
相同，则存在唯一的次数不超过n-1的多
1
项式 ，满足
0,1,...,
),......(
x
n
,
y
1
n
( )A x
,
x x
0
1
,...,
x
1
n
)}
n
1
y
k
(
A x
k
)
k
continue
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
