《算法导论》读书笔记 kirai 17/06/18 第30章 多

这部分是关于ＤＦＴ和ＩＤＦＴ的。
　　首先是单位复数根的定义，根据欧拉公式，将θ拆分为n份，那么每一个分割点在极坐标系下表示为e^{ik2π/n}，即第 k个切分点，其中k属于[0,n-1]。
　　书上讲，{w^k_n, ·}实际上是一个群，简便起见，我仅证明了一下它的封闭性：
　　求w_n^I·w_nJ。
　　讨论两种情况，I+J<=n-1和>=n的情况。第一种显而易见封闭。第二种可以替换成(I+J)%n的形式，并且附加一个w^{n_n，定义知w}n_n=1，因此此式转换为w_n^{(I+J)%n}