文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载导读本文围绕 CLRS 仓库中 docs/Chap30/30.2.md 记录的《Introduction to Algorithms》第三版第 30 章第 2 节全部 8 道习题展开先交代离散傅里叶变换DFT与快速傅里叶变换FFT的记号体系与核心定理再逐题给出完整的推导过程与可直接复算的数值结果最后把各题与仓库内相关章节30.1、30.3 及 Problems 30-1/30-2/30-5/30-6、17-1串联起来帮助读者从「会背公式」进阶到「能独立推导、能亲手算例、能读懂高效实现」。读完后你将掌握逆 DFT 的闭式证明、FFT 的多路分治推广含 n 为 3 的幂的情形、基于模运算的无误差 FFTNTT 思想的雏形、用分治构造零点多项式以及把 chirp 变换化为一次卷积从而在 O(n lg n) 时间内求值的完整手法。一、本节背景记号、DFT 定义与两个核心定理仓库的导航配置 mkdocs.yml 将本文件收录为「30.2 The DFT and FFT」其主题是整章「Polynomials and the FFT」的核心把多项式从系数表示切换到点值表示用 O(n lg n) 时间完成求值与插值。本节沿用全书的记号约定主 n 次单位根$\omega_n e^{2\pi i/n}$满足 $\omega_n^n 1$ 且对 $1 \le k n$ 有 $\omega_n^k \ne 1$称 $\omega_n$ 为本原n 次单位根向量 $a (a_0, a_1, \dots, a_{n-1})$ 的 DFT 定义为$$y_k \sum_{j0}^{n-1} a_j \omega_n^{kj}, \qquad k 0, 1, \dots, n-1;$$若记 $V_n$ 为 $(V_n)_{kj} \omega_n^{kj}$ 的矩阵则 DFT 就是矩阵乘法 $y V_n a$。FFT 之所以能做到 $\Theta(n\lg n)$本质上是利用 $\omega_n$ 的对称性把长度为 n 的 DFT 拆成两个长度为 n/2 的 DFT奇偶下标分解得到递推 $T(n) 2T(n/2) \Theta(n) \Theta(n\lg n)$第 30.3 节 docs/Chap30/30.3.md 进一步讨论 ITERATIVE-FFT 等工程化实现本节的习题 30.2-5 则把这一思想推广到三路分治。二、30.2-1证明 Corollary 30.4逆 DFT 的闭式表达题目证明 Corollary 30.4。Corollary 30.4 断言 $V_n$ 可逆且逆矩阵具有显式形式$$(V_n^{-1})_{kj} \frac{\omega_n^{-kj}}{n},$$等价地写作 $V_n^{-1} \frac{1}{n},\overline{V_n}$逐元素共轭。这正是逆 DFT 公式$$a_j \frac{1}{n}\sum_{k0}^{n-1} y_k \omega_n^{-kj}$$的来源。证明。关键是单位根的正交性对任意整数 $i, j$有$$\sum_{k0}^{n-1} \omega_n^{k(i-j)} \begin{cases} n, i j, \ 0, i \ne j. \end{cases}$$当 $i j$ 时每一项都是 1和为 n当 $i \ne j$ 时$\omega_n^{i-j} \ne 1$因为 $\omega_n$ 是本原单位根且 $i - j$ 不是 n 的倍数于是按等比数列求和公式$$\sum_{k0}^{n-1} \omega_n^{k(i-j)} \frac{\omega_n^{n(i-j)} - 1}{\omega_n^{i-j} - 1} \frac{1 - 1}{\omega_n^{i-j} - 1} 0.$$现在把逆变换的候选表达式作用于任意 $y V_n a$$$\frac{1}{n}\sum_{k0}^{n-1} y_k \omega_n^{-kj} \frac{1}{n}\sum_{k0}^{n-1}\left(\sum_{i0}^{n-1} a_i \omega_n^{ki}\right)\omega_n^{-kj} \sum_{i0}^{n-1} a_i \cdot \frac{1}{n}\sum_{k0}^{n-1}\omega_n^{k(i-j)} a_j.$$即 $V_n^{-1} \frac{1}{n}\overline{V_n}$ 确实满足 $V_n^{-1}V_n I$。证明完成。这个结论是 30.2-4 设计逆 DFT 算法的直接理论依据。三、30.2-2计算向量 (0, 1, 2, 3) 的 DFT题目计算向量 $(0, 1, 2, 3)$ 的 DFTn 4$\omega_4 e^{2\pi i/4} i$。按定义逐项展开下标 j 从 0 到 3$$y_0 0 1 2 3 6,$$$$y_1 \omega_4 2\omega_4^2 3\omega_4^3 i 2(-1) 3(-i) -2 - 2i,$$$$y_2 \omega_4^2 2\omega_4^4 3\omega_4^6 -1 2 3(-1) -2,$$$$y_3 \omega_4^3 2\omega_4^6 3\omega_4^9 -i 2(-1) 3i -2 2i.$$因此$$\text{DFT}((0,1,2,3)) (6,\ -2-2i,\ -2,\ -22i).$$验算利用 Corollary 30.4 做逆变换$(1/4)\sum_k y_k \omega_4^{-kj}$ 应还原出 $(0,1,2,3)$。例如 $j1$$\tfrac14(6 - (-2-2i)\cdot i - (-2)(-1) - (-22i)(-i)) \tfrac14(6 (-2i2) 2 (2i2)) \tfrac14 \cdot 4 1$其余分量同理正确还原。这个小例子同时验证了 DFT 与逆 DFT 互为可逆操作。四、30.2-3用 Θ(n lg n) 方案重做 Exercise 30.1-1题目用 $\Theta(n\lg n)$ 时间的方案完成 Exercise 30.1-1 的多项式乘法。Exercise 30.1-1其完整解答见 docs/Chap30/30.1.md要求计算$$A(x) 7x^3 - x^2 x - 10, \qquad B(x) 8x^3 - 6x 3$$的乘积直接按系数卷积得到 $56x^6 - 8x^5 - 34x^4 - 53x^3 - 9x^2 63x - 30$。这里要求改用第 30.2 节的 $\Theta(n\lg n)$ 方案即「系数表示 → 点值表示 → 点值相乘 → 插值」四步两个多项式次数均为 3乘积次数上界为 6因此取 n 82 的幂把系数填充到长度 8$a (7,-1,1,-10,0,0,0,0)$$b (8,0,-6,3,0,0,0,0)$用 FFT 在 8 个 8 次单位根 $\omega_8^k$ 处求值得 $Y_a \text{FFT}(a)$、$Y_b \text{FFT}(b)$点值相乘$Y_c[k] Y_a[k] \cdot Y_b[k]$$k 0, \dots, 7$对 $Y_c$ 做逆 DFT30.2-4 的方法取实部即得乘积系数。数值复算numpy 卷积与 FFT 两条路径交叉验证结果一致$$(56,\ -8,\ -34,\ -53,\ -9,\ 63,\ -30,\ 0)$$即 $56x^6 - 8x^5 - 34x^4 - 53x^3 - 9x^2 63x - 30$与 docs/Chap30/30.1.md 中按公式 (30.1)/(30.2) 直接展开的答案完全相同。这里体现了「点值相乘是逐点标量乘法代价 O(n)」这一关键优势复杂度瓶颈完全落在两次 FFT 与一次逆 FFT 上总计 $\Theta(n\lg n)$。五、30.2-4Θ(n lg n) 时间的逆 DFT 伪代码题目写出在 $\Theta(n\lg n)$ 时间内计算 $\text{DFT}_n^{-1}$ 的伪代码。由 Corollary 30.4逆 DFT 无非是「以 $\omega_n^{-1}$ 为单位根做一次 FFT再逐项除以 n」。CLRS 风格的伪代码如下INVERSE-DFT(y) n y.length ωn⁻¹ e^{-2πi/n} // 即 ω_n 的复共轭 a RECURSIVE-FFT(y, ωn⁻¹) // 用 ωn⁻¹ 替换 ω_n 递归执行 FFT for j 0 to n - 1 a_j a_j / n return a等价且工程上更常用的写法是利用共轭对称性把逆 DFT 完全复用在正向 FFT 例程上$$a_j \frac{1}{n},\overline{\text{FFT}\big(\overline{y}\big)},$$即「先逐项取共轭 → 做正向 FFT → 再逐项取共轭并除以 n」。对上一题 $y (6, -2-2i, -2, -22i)$ 用该技巧复算可精确还原 $(0,1,2,3)$验证了正确性。两种写法时间均为 $\Theta(n\lg n)$与正向 FFT 同阶。六、30.2-5把 FFT 推广到 n 为 3 的幂并解递推题目把 FFT 过程推广到 n 为 3 的幂的情形给出运行时间的递推并求解。推广思路把下标按模 3 的余数分成三组$j \equiv 0, 1, 2 \pmod 3$对应三个长度为 n/3 的多项式$$A^{(r)}(x) \sum_{j \equiv r \pmod 3} a_j x^{j/3}, \qquad r 0, 1, 2.$$对任意 $k$把 $\omega_n^k$ 代入 $A(x) \sum_r x^r A^{(r)}(x^3)$$$y_k A(\omega_n^k) A^{(0)}(\omega_n^{3k}) \omega_n^k A^{(1)}(\omega_n^{3k}) \omega_n^{2k} A^{(2)}(\omega_n^{3k}).$$注意到 $\omega_n^{3k} \omega_{n/3}^k$而 $\omega_{n/3}$ 是 n/3 次本原单位根所以 $A^{(r)}(\omega_n^{3k})$ 正是长度为 n/3 的 DFT 在索引 $k \bmod (n/3)$ 处的取值。于是递归计算三个 n/3 规模的 DFT$y^{(0)}, y^{(1)}, y^{(2)}$对每个 $k 0, \dots, n-1$用上式把三个结果以 $\omega_n^k$、$\omega_n^{2k}$ 为权组合每个 k 常数次乘加。合并阶段共 O(n) 次运算故递推为$$T(n) 3T(n/3) \Theta(n).$$由主定理情形 2$\log_3 3 1$解为 $T(n) \Theta(n\lg n)$与 n 为 2 的幂时同阶。本题的意义在于说明FFT 的分治结构不依赖「2」任意固定因子 r 的 r 路分治都能得到 $\Theta(n\lg n)$第 30.3 节的 ITERATIVE-FFT 与位反转排列见 docs/Chap17/Problems/17-1.md 中 rev_k 的定义则是 2 路情形的工程化落地。七、30.2-6 ★在环 Z_m 上的模 DFTFermat 型模数题目设 n 为偶数考虑整数模 m 的环 $\mathbb Z_m$其中 $m 2^{tn/2} 1$t 为任意正整数。用 $\omega 2^t$而不是 $\omega_n$作为模 m 的本原 n 次单位根。证明 DFT 与逆 DFT 在此系统中良定义。证明分三步。第一步$\omega 2^t$ 是模 m 的本原 n 次单位根。因为$$\omega^n 2^{tn} \big(2^{tn/2}\big)^2 (m - 1)^2 \equiv 1 \pmod m,$$且 $\omega^{n/2} 2^{tn/2} m - 1 \equiv -1 \not\equiv 1 \pmod m$。进一步对 $1 \le j \le n/2 - 1$有 $0 \omega^j 2^{tj} 2^{tn/2} m - 1$故 $\omega^j \not\equiv 1$对 $n/2 j n$利用 $\omega^j \omega^n \omega^{j-n} \equiv \omega^{-(n-j)} \pmod m$若 $\omega^j \equiv 1$ 则 $\omega^{n-j} \equiv 1$ 且 $1 \le n - j \le n/2 - 1$矛盾。因此 $\omega^j \not\equiv 1$ 对一切 $1 \le j \le n - 1$ 成立$\omega$ 确为本原 n 次单位根。第二步n 在 $\mathbb Z_m$ 中可逆。n 为偶数本书语境下取 2 的幂而 m 2^{tn/2} 1 是奇数故 $\gcd(n, m) 1$1/n 在模 m 下有定义。第三步正交性成立逆矩阵可显式给出。对 $i \ne j$$\omega^{i-j}$ 是不同于 1 的 n 次单位根等比求和得 $\sum_{k0}^{n-1}\omega^{k(i-j)} \equiv 0 \pmod m$于是 $V_n^{-1} \frac{1}{n}(\omega^{-kj})$ 满足 $V_n^{-1}V_n I$DFT 与逆 DFT 构成互逆运算良定义。数值验证取 n 4t 2$m 2^{4} 1 17$$\omega 2^2 4$。检查本原性$4^4 256 \equiv 1 \pmod{17}$$4^2 16 \equiv -1 \pmod{17}$。对向量 $(0,1,2,3)$ 做模 17 的 DFT$$y_0 6,\quad y_1 4 2\cdot 16 3\cdot 64 \equiv 7,\quad y_2 16 2\cdot 256 3\cdot 4096 \equiv 15,\quad y_3 64 2\cdot 4096 3\cdot 262144 \equiv 6,$$即 $\text{DFT}_{17}((0,1,2,3)) (6, 7, 15, 6)$再用 $(1/4)(\omega^{-kj})$ 做逆变换模 17 下 $4^{-1} 13$精确还原 $(0,1,2,3)$。全程只有整数运算、无浮点误差——这正是「模 FFT」的价值。与仓库其他内容的联系本题是 docs/Chap30/Problems/30-6.mdFFT using modular arithmetic数论变换 NTT的先导那里改用素数 $p kn 1$ 与生成元 g取 $\omega g^k \bmod p$使模长仅 $O(\lg n)$ 位从而能无误差地做整数系数多项式乘法而 30.2-6 的模数长 $\Omega(n)$ 位是更直接但更昂贵的一种方案。两者共用「本原单位根 1/n 可逆 正交性」的同一证明骨架与第 31 章数论基础见 docs/Chap31衔接。八、30.2-7O(n lg² n) 构造在给定点取零的多项式题目给定可重复的值 $z_0, z_1, \dots, z_{n-1}$构造次数界为 $n1$、仅在 $z_j$ 处取零的多项式 $P(x)$运行时间 $O(n\lg^2 n)$。提示$P(x)$ 在 $z_j$ 处取零当且仅当 $P(x)$ 是 $(x - z_j)$ 的倍数。解法。满足条件的多项式为$$P(x) \prod_{j0}^{n-1} (x - z_j).$$直接逐个乘是 $O(n^2)$ 次卷积运算需要加速。采用分治把点集对半分成 $Z_L {z_0, \dots, z_{\lceil n/2\rceil-1}}$ 与 $Z_R$递归计算两个半程乘积 $P_L \prod_{z \in Z_L}(x-z)$、$P_R \prod_{z \in Z_R}(x-z)$再合并$$P P_L \cdot P_R,$$而一次合并是两个次数至多 n/2 的多项式相乘可用 FFT 在 $O(n\lg n)$ 内完成。递推为$$T(n) 2T(n/2) O(n\lg n),$$展开得 $T(n) O(n\lg^2 n)$满足题目要求。若允许重复零点本解同样成立因为重复的点在乘积中以相同因式出现多次。数值验证取 $z (1, 2, 3, 4)$分治合并每次合并用一次卷积得到升幂系数 $(24, -50, 35, -10, 1)$即$$P(x) (x-1)(x-2)(x-3)(x-4) x^4 - 10x^3 35x^2 - 50x 24,$$在 1、2、3、4 处均取 0正确。对称的另一面把「一次多项式相乘构造乘积树」倒过来就得到多点求值。仓库中的 docs/Chap30/Problems/30-5.md 正是用同样的分治树在 $O(n\lg^2 n)$ 时间内把次数界 n 的多项式在 n 个任意点求值利用 $A \bmod P_{ij}$ 的余数逐层下推30.2-7 与 30-5 合在一起构成了「分治求值—分治插值」的完整对称图景也解释了为什么第 30 章的多项式运算能做到近乎线性的复杂度。九、30.2-8 ★Chirp 变换的 O(n lg n) 求值题目向量 $a (a_0, \dots, a_{n-1})$ 的chirp 变换是向量 $y$其中$$y_k \sum_{j0}^{n-1} a_j z^{kj},$$z 为任意复数。DFT 恰是 $z \omega_n$ 时的特例。证明对任意复数 zchirp 变换都可在 $O(n\lg n)$ 时间内求值。提示用恒等式$$y_k z^{k^2/2} \sum_{j0}^{n-1} \big(a_j z^{j^2/2}\big)\big(z^{-(k-j)^2/2}\big)$$把 chirp 变换看作卷积。关键观察利用指数恒等式 $kj \frac{k^2 j^2 - (k-j)^2}{2}$得$$z^{kj} z^{k^2/2}, z^{j^2/2}, z^{-(k-j)^2/2},$$于是$$y_k z^{k^2/2} \sum_{j0}^{n-1} b_j, c_{k-j}, \qquad b_j a_j z^{j^2/2},\quad c_{k-j} z^{-(k-j)^2/2}.$$右侧正是序列 $b (b_0, \dots, b_{n-1})$ 与 $c (c_{-(n-1)}, \dots, c_{n-1})$按 $k - j$ 索引、长度 $2n-1$的卷积在位置 k 处的取值。算法计算 $b_j a_j z^{j^2/2}$O(n)构造 $c_m z^{-m^2/2}$$m -(n-1), \dots, n-1$O(n)用两次 FFT实际等价于把 $b$、$c$ 填充到长度 $\ge 2n$ 后做一次多项式乘法在 $O(n\lg n)$ 内算出卷积 $d_k \sum_j b_j c_{k-j}$输出 $y_k z^{k^2/2} d_k$O(n)。总计 $O(n\lg n)$且对任意复数 z包括 $|z| 1$ 的 DFT 情形都成立。数值验证取 n 4$z \omega_4 i$$a (0,1,2,3)$。直接求和得到 $(6, -2-2i, -2, -22i)$——与 30.2-2 的 DFT 结果一致因为 $z \omega_4$ 时 chirp 就是 DFT再按上述卷积路线$b_j a_j i^{j^2/2}$$c_m i^{-m^2/2}$做一次完整卷积后取 $d_k$ 并乘 $z^{k^2/2}$复算两条路径逐点吻合误差 1e-15。对随机复数 $z 0.5 0.7i$、n 5 再验证一次直接求值与卷积求值同样完全一致。chirp 变换把「一般底数的离散幂求和」化为「一次标准卷积」是信号处理中 chirp-z 变换CZT的理论基石也再次展示了第 30 章的核心思想凡是能化成卷积的求和都可以借 FFT 提速到 O(n lg n)。仓库中的 docs/Chap30/Problems/30-2.mdToeplitz 矩阵乘向量正是同一思想的另一处应用。十、延伸阅读本节习题在仓库中的坐标CLRS 仓库README.md《Introduction to Algorithms》第三版习题解答集围绕第 30 章形成了完整的文档族可与本节习题对照阅读表示基础docs/Chap30/30.1.md —— 系数表示/点值表示的互转、插值唯一性Theorem 30.1以及 30.1-1 的直接卷积答案30.2-3 的对标物高效实现docs/Chap30/30.3.md —— ITERATIVE-FFT、位反转排列、蝴蝶电路其中 30.3-3 讨论每阶段 twiddle factor 的计算次数阶段 s 从 $2^s - 1$ 次降到 $2^{s-1}$ 次是 30.2-5 分治思想的工程化延伸分治乘法docs/Chap30/Problems/30-1.md —— 高/低位与奇偶下标两种 $\Theta(n^{\lg 3})$ 乘法Karatsuba 型与 FFT 乘法互为正交的优化路线卷积与矩阵docs/Chap30/Problems/30-2.md —— Toeplitz 矩阵乘向量化为一次卷积与 30.2-8 的卷积化手法同源多点求值docs/Chap30/Problems/30-5.md —— 与 30.2-7 对称的 $O(n\lg^2 n)$ 多点求值余数分治树模 FFTdocs/Chap30/Problems/30-6.md —— 30.2-6 的进阶版用素数模 $p kn1$ 实现无误差整数卷积NTT位反转docs/Chap17/Problems/17-1.md —— FFT 第一步的 bit-reversal permutation 及其摊还分析与 30.3 的迭代实现配套。若在移动端阅读本文档仓库已通过 mkdocs.yml 配置 KaTeX 与横向滚动样式数学公式均可正常渲染各习题的原始陈述与官方占位说明见 docs/Chap30/30.2.md。小结30.2 这一节的 8 道习题构成一条完整的能力链30.2-1/30.2-4 打通「逆 DFT 的证明与算法」30.2-2/30.2-3 提供「手算 机算」双重验证30.2-5/30.2-6 展示「分治推广与模算术落地」30.2-7/30.2-8 则把 FFT 的力量延伸为「分治多项式运算」与「卷积化的任意求和」。掌握这组习题就掌握了《算法导论》中 FFT 一章从理论到工程的核心脉络——无论是数值计算中的卷积、数论中的 NTT还是信号处理里的 chirp-z 变换其底层的复杂度原理都源于这里。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐CLRS Solutions 详解《算法导论》第 1 章 1.1 节习题 1.1-11.1-5 的答案与延伸解析CLRS Solutions 详解《算法导论》第 1 章 1.1 节习题 1.1 11.1 5 的答案与延伸解析 本文基于 CLRS 仓库中的 docs/C文档教程教育CLRS《算法导论》第 4.1 节习题精解代入法求解递归式的完整实战CLRS《算法导论》第 4.1 节习题精解代入法求解递归式的完整实战 本文基于开源仓库 gh_mirrors/cl/CLRS Solutions to In文档教程示例工程CLRS 第 4.2 节精解Strassen 矩阵乘法算法推导、伪代码与习题全解CLRS 第 4.2 节精解Strassen 矩阵乘法算法推导、伪代码与习题全解 导读 本文围绕《算法导论第三版》第 4.2 节 Strassens a文档教程教育上一篇FerretDB 测试实战在传统 mongo shell 中使用断言编写可复现测试下一篇如何用NS-USBLoader轻松管理Switch游戏文件新手必看的5个实用技巧创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考