前言：关于为什么要写这个博客
最近在重新看《合成孔径雷达成像 算法与实现》这本书，看到“离散傅里叶变换记其逆变换的运算量级为”这句话，就想起当初在学《数字信号处理》中FFT那章节时，书中有对比DFT和FFT的运算量的一些文字，完全想明白那个推导过程还是费了点劲儿的。再就是最近我的《数字图像处理》老师提到，要对比不同算法干一件事儿的效率，首先是要将两种算法的运算量或者说复杂度定量地表示出来（这个不能拿计算机处理数据的总时长来说事儿哈）。于是我萌生了写一个入门级别运算量分析和计算的博客，但是这里面会带入很多基础知识，所以对像我一样菜的人会比较友好，不过稍显冗余。
正文
一、一维信号的运算量
1.DFT/IDFT运算量说明
给定一个序列g(n)，初学的时候序列都是实序列，但是为了更一般一点儿，我想将其设定为复序列（就是说每个元素都是复数，可以写成的标准形式）。首先我要扔出DFT/IDFT变换的两个公式：
(1)
(2)
其中，，且只取整数（下面就不再强调了）。
对（1）而言，k每取一个值（当然这个值的范围只能是[0,N-1]中的整数），比如k就取个2吧，那完整表达式就是：
（3）
（按照顺序来看）
可以利用欧拉公式，将写成的形式，因此单单（3）这一个计算式，就要完成N次复乘和N-1次复加。而k可以取遍0~N-1这N个整数值，就是把上边那个过程重复了N次，我把这个计算过程稍微呈现一下：
（4）
（按照顺序来看）
我还想进一步地用矩阵来表示这个过程：
（按照顺序来看）
不难看出，整个计算过程要经历次复乘和N*(N-1)≈次复加，相同地，IDFT的运算量与DFT是一样的。
结论就是，“离散傅里叶变换及其逆变换的运算量级为”。
2.FFT/IFFT运算量说明
到这个时候，书上往往就开始讲为什么要寻找一种新的离散傅里叶变换算法(即FFT)，说什么“DFT运算量太大，计算耗时特别长”云云，而我要说说为什么能够提出FFT，其实很简单，就一句话：因为具有非常好的数学特性。举个例子，最常见的复指数函数,随着时间的推移，变量与函数值对应的坐标点一直在单位圆上转圈圈，存在,这呈现出良好的周期性。下面给出关于的一些重要数学特性：
首先明确这样几个式子：
(5)
2.1 周期性：
对n的周期性：
对k的周期性：
2.2 对称性：
对n的对称性：
对k的对称性：
2.3其他性质
对n的性质：
对k的性质：
有了这些作为基础，FFT的过程就好理解了。再拿DFT的定义式说事儿，这次令时域序列为x(n),频域序列为X(k)：
假设序列长度N是2的整次幂（后面解释为什么是2的整次幂；显然N是个偶数），序列标号为0~N-1，现在来推导基2 FFT。将序列x(n)中的奇数标号的序列和偶数标号的序列分别提取出来，组成如下两个新的序列：
(6)
值得注意的是，这两个序列的长度都是。计算X(k)是将整个序列x(n)分别与对应因子相乘后求和，这也可以将序列的奇数标号部分和偶数标号部分分开，分别来做这个计算再求和（这就好比你要计算1+2+3+4+5+6+7+8，就等同于算(1+3+5+7)+(2+4+6+8))，计算过程就是：
代入刚刚分出来的俩序列（6），得：
再用一下2.3中提到的其它性质，将指数分子上的2倍变成分子上的1/2，即：
(注意，从这里开始k的范围悄悄变成了)
巧妙的是，我们分出来的序列每个都长，这就意味着，上面的结果等于的离散傅里叶变换与的离散傅里叶变换乘一个因子的和，即为：
这了不得呀！欲求一个长度为N的序列的离散傅里叶变换，拆解成了求两个长度均为的序列的离散傅里叶变换，再经过加权求和就能得到。。。。。
（累了，择日继续写）
