數位訊號處理基礎
假設N點的DFT依定義計算約需 N² 次運算，以FFT（快速傅立葉轉換）則約需 N log₂N 次。N = 1024 時，FFT減少運算次數的程度最接近下列何者？
- A約10分之1
- B約100分之1
- C約1000分之1
查看答案與解析
正確答案：B. 約100分之1
N² = 1024² ≈ 105萬，N log₂N = 1024 × 10 = 10240，比為 N/log₂N = 1024 ÷ 10 = 102.4，也就是約100分之1。N 越大差距越大，例如 N = 65536 時約為4096分之1。FFT把DFT依序分解成一半大小的DFT，並把共同的計算合併，藉此減少運算。
- A. 這是 log₂N = 10 的值。比為 N²/(N log₂N) = N/log₂N。
- B. 正確。1024 ÷ 10 = 102.4，約100分之1。
- C. 這是假設FFT的運算次數為 N 次時的比（N²/N = 1024）。