演算法›Ch2 分治法第 3 題/共 12 題
3. FFT、分治法
#AL-02-003易FFT分治法
Which property of the root of unity , where is a power of 2, allows the Cooley-Tukey fast-fourier transform algorithm to achieve its speedup in time complexity?
參考答案與解析
答案 (B):FFT 的關鍵在於單位根的對稱性 W_n^{k+n/2} = -W_n^k,這讓 DFT 可以把長度 n 的問題拆成兩個長度 n/2 的子問題(偶數項、奇數項),遞迴式 T(n)=2T(n/2)+O(n),才能達到 O(n log n)。
📄 台大115
▤完整推導請見《WH 資工筆記 · 演算法》Ch2 分治法