| 用分治及贪婪策略实现FFT整序 |
| |
| 引用本文： | 贾渊,范勇,刘渊,赵文琦.用分治及贪婪策略实现FFT整序[J].江苏科技大学学报(社会科学版),2008,22(5). |
| |
| 作者姓名： | 贾渊 范勇 刘渊 赵文琦 |
| |
| 作者单位： | 西南科技大学计算机学院,四川绵阳621010 |
| |
| 基金项目： | 国家自然科学基金资助项目，国家863资助项目，校博士基金资助项目，校十一五重点资助项目 |
| |
| 摘 要： | FFT整序的关键是逆序号的求取,用预先存贮的逆序表可提高FFT整序的效率.算法结合分治与贪婪策略,用最少的交换次数得到逆序表.算法避免了常规整序中顺序号与逆序号的比较运算, 提高了FFT整序的效率.为了比较相关算法在Windows操作系统下的运行效率,编制了相应的C 程序.实验表明,求取长2N的逆序表时,算法的交换次数为数组长的一半(2N-1-1或2N-1-2),其效率优于传统的整序算法.
|
| 关 键 词： | FFT整序 分治法 贪婪策略 逆序 |
FFT permutation algorithm with divide-and-conquer and greedy strategy |
| |
| JIA Yuan,FAN Yong,LIU Yuan,ZHAO Wenqi.FFT permutation algorithm with divide-and-conquer and greedy strategy[J].Journal of Jiangsu University of Science and Technology:Natural Science Edition,2008,22(5). |
| |
| Authors: | JIA Yuan FAN Yong LIU Yuan ZHAO Wenqi |
| |
| Institution: | JIA Yuan,FAN Yong,LIU Yuan,ZHAO Wenqi(School of Computer Science , Technology,Southwest University of Science , Technology,Mianyang Sichuan 621010,China) |
| |
| Abstract: | How to rapidly obtain the inverse number is one of the most important steps in FFT permutation.With an array storing some inverse order numbers of the indices beforehand,the permutation algorithm performance may be improved.This paper presents an algorithm with divide-and-conquer and greedy strategy,and the inverse order array can be obtained with least exchange times.The algorithm avoids the comparison operations that need to be implemented in general permutation algorithm.Therefore,the algorithm performan... |
| |
| Keywords: | FFT permutation divide-and-conquer greedy strategy inverse order |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
