偏微分方程中傅丽叶变换的方法1直接计算DFT的运算量问题设x(n)为N点有限长序列,其DFT为k=0,1,…,N-1(9-1)反变换(IDFT)为n=0,1,…,N-1(9-2)二者的差别只在于WN的指数符号不同,以及差一个常数乘因子1/N,所以IDFT与DFT具有相同的运算工作量。下面我们只讨论DFT的运算量。一般来说,x(n)和WNnk都是复数,X(k)也是复数,因此每计算一个X(k)值,需要N次复数乘法和N-1次复数加法。而X(k)一共有N个点(k从0取到N-1),所以完成整个DFT运算总共需要N2次复数乘法及N(N-1)次复数加法。在这些运算中乘法运算要比加法运算复杂,需要的运算时间也多一些。因为复数运算实际上是由实数运算来完成的,这时DFT运算式可写成由此可见,一次复数乘法需用四次实数乘法和二次实数加法;一次复数加法需二次实数加法。因而每运算一个X(k)需4N次实数乘法和2N+2(N-1)=2(2N-1)次实数加法。所以,整个DFT运算总共需要4N2次实数乘法和2N(2N-1)次实数加法。当然,上述统计与实际需要的运算次数稍有出入,因为某些WNnk可能是1或j,就不必相乘了,例如W0N=1,WNN/2=-1,WNN/4=-j等就不需乘法。但是为了便于和其他运算方法作比较,一般都不考虑这些特殊情况,而是把WNnk都看成复数,当N很大时,这种特例的影响很小。从上面的统计可以看到,直接计算DFT,乘法次数和加法次数都是和N2成正比的,当N很大时,运算量是很可观的,有时是无法忍受的。2改善途径能否减少运算量,从而缩短计算时间呢?仔细观察DFT的运算就可看出,利用系数WNnk的以下固有特性,就可减少运算量:这样,利用这些特性,使DFT运算中有些项可以合并,并能使DFT分解为更少点数的DFT运算。而前面已经说到,DFT的运算量是与N2成正比的,所以N越小越有利,因而小点数序列的DFT比大点数序列的DFT的运算量要小。偏微分方程中傅丽叶变换的方法
上一篇：选择排序（数据结构）