← 返回首頁

FFT 快速傅立葉變換視覺化

多項式乘法流程

1. 係數表示 2. 點值表示 (FFT) 3. 結果係數 (IFFT)
A(x):
B(x):

蝴蝶運算 (Butterfly Operations)

選擇係數後開始

點值乘法

多項式表示

A(x) = ...
B(x) = ...
-
FFT 大小 (N)
-
蝴蝶階段
-
蝴蝶運算
0 / 0
Frame

Before / After 比較

暴力多項式乘法 O(n^2)

尚未計算

FFT 多項式乘法 O(n log n)

尚未計算
FFT - Cooley-Tukey Algorithm
時間複雜度
O(n log n)
空間複雜度
O(n)
應用
多項式乘法、大整數乘法、訊號處理
核心思想
分治：將偶數項與奇數項分開遞迴計算