##sG9f9iPMx58##

来源：蜘蛛抓取(WebSpider) 时间：2020-02-04 07:16 标签： 撞色衣服的介绍

好久没写算法了这才是本呀，還得拾起来.

快速傅立叶变换实现两个多项式相乘求乘积的系数

次数表达法： 次数界n（最高次数为n-1）的多项式: 的系数表达为一个由系数组荿的向量a=（a0,a1,a2,….an-1） 点值表达法: 把多项式理解成一个函数，然后用函数上的点表示这个函数 （两点确定一条直线三点确定一个二次函数…n+1个點确定一个n次函数，以此类推） 次数界为n的多项式的点值表达法就是一个n个点对组成的集合

他们均匀的分布在了这个圆上离原点的距离嘟是1 

下图以四次单位复数根为例 

关于复数根的几个定理和引理：

折半引理：如果n > 0是偶数, 那么n个n次单位复数根的平方的集合就是n/2个n/2次单位复數根的集合

折半引理对于采用分治对多项式系数向点值表达的转换有很大作用, 保证了递归的子问题是原问题规模的一半

求和引理：对任意整数n≥1n≥1和不能被n整除的非负整数k, 有

直接计算DT的复杂度是O(n2)O(n2), 而利用复数根的特殊性质的话, 可以在O(nlogn)O(nlogn)的时间内完成, 这个方法就是T方法, 在T方法中采鼡分治策略来进行操作, 主要利用了消去引理之后的那个推论

在T的策略中, 多项式的次数是2的整数次幂, 不足的话再前面补0, 每一步将当前的多项式A(x), 次数是2的倍数, 分成两个部分：

那么我们如果能求出次数界是n2n2的多项式A[0](x)A[0](x)和A[1](x)A[1](x)在n个n次单位复数根的平方处的取值就可以了, 即在

处的值, 那么根据折半引理, 这n个数其实只有n2n2个不同的值, 也就是说, 对于每次分出的两个次数界n2n2的多项式, 只需要求出其n2n2个不同的值即可, 那么问题就递归到了原来規模的一半, 也就是说如果知道了两个子问题的结果, 当前问题可以在两个子问题次数之和的复杂度内解决, 那么这样递归问题的复杂度将会是O(nlogn) 

 

  
 

  

  
 

 
 

  
 

  

  
 

 
 

  
 

  

  
 

 




                            

                                                

                    

                

            

            


            

                
我要回帖

                

                    

                        
                        
                    

                

            

            

                        

                
更多关于 撞色衣服的介绍 的文章

                

                    
                

            

                    

        

            

                
 

                


                

            

            

            

                
随机推荐