用分治及贪婪策略实现FFT整序.pdfVIP

第 22卷第 5期 江 苏 科 技 大学 学 报(自然科学版) Vo1．22 No．5 2008年 10月 JournalofJiangsuUniversityofScienceandTechnology(NaturalScienceEdition) 0ct．2008 用分治及贪婪策略实现FFT整序 贾 渊，范 勇，刘 渊，赵文琦 (西南科技大学计算机学院，四J 绵阳621010) 摘 要：FFr整序的关键是逆序号的求取，用预先存贮的逆序表可提高 FFT整序的效率．算法结合分治与贪婪策略，用 最少的交换次数得到逆序表．算法避免了常规整序中顺序号与逆序号的比较运算，提高了FFTr整序的效率．为了比较相 关算法在Windows操作系统下的运行效率，编制了相应的c++程序．实验表明，求取长2 的逆序表时，算法的交换次数 为数组长的一半(2 一l或2 一2)，其效率优于传统的整序算法． 关键词：FFT整序；分治法；贪婪策略；逆序 中图分类号：TP31 文献标识码 ：A 文章编号 ：1673—4807(2008)05—0059—04 FFT permutationalgorithm with divide-and-conquerandgreedystrategy JIAYuan，FANYong，LIUYuan，ZHAOWenqi (SchoolofComputerScienceandTechnology，SouthwestUniversityofScienceandTechnology，MianyangSichuan621010，China) Abstract：How torapidlyobtaintheinversenumberisoneofthemostimportantstepsinFFYrpermutation． Withanarraystoring someinverseordernumbersoftheindicesbeforehand，thepemr utationalgorithm per- fomr aneemaybe improved．Thispaperpresentsan algorithm with divide—and—conquerand greedystrategy， andtheinverseorderarraycanbeobtainedwithleastexchangetimes．Thealgorithm avoidsthecomparison operationsthatneedtobeimplementedingeneralpermutationalgorithm．Therefore，thealgorithm perfomr ance issuperiortothatofthegenera1．Inordertotestitsperfomr anceinwindowsoperationsystem ，severalrelative algorithmsareprogrammedwithC ++ languageattheVC2003．netplatfomr ．and theiroperation timesare compared．Theexperimentsshow theexchangetimeswillbe2 ～ 一1or2 ～ 一2iftheinverseorderarray lengthis2 ，whichmeansthattheperfomr anceofthisalgorithm introducedinthepaperisbetterthanthatof thetraditionalpermutationalgorithms． Keywords：FFTpermutation；divide-and-conquer；rgeedystrateyg ；inverseorder 0 引 言 随着计算机的小型化及性能的不断提升，尤其是面向对象的编程技术和Windows操作系统的普及，许 多基于机器视觉或图像分析来实现工业产品的自动检测研究在Pc机上就可以实现．傅氏变换作为重要的 分析工具之一，尤其是离散小波变换可经由其实现…，使得研究者为提升效率进行了多种改进．但是不