快速演算法設計的原則



快速演算法設計原理
快速演算法的主要目標為節省計算時間，採取手段主要如下：
減少加法數量
減少乘法數量
減少迴圈數量
其中以減少乘法數量最為重要，可以最為高效率節省計算量。

快速演算法的設計重要的四種概念

N-point DFT
對於任何點數的離散傅立葉轉換(DFT)，都有其適合的快速演算法．

線性非時變系統的運算複雜度
由於線性非時變系統可以用卷積Convolution來表示，故我們可以說其運算複雜度為，三個傅立葉轉換的計算量（包括兩個FTs 以及一個IFT)
⇒
⇒
若使用了快速演算法，我們可以將其運算複雜度降為

Replacement of DFTs
對於DFT的計算有複數(complex number)的問題，我們也可以透過矩陣的方式來處理．

運算簡化技巧
下面以四個例子來解說：

(1) 
⇒
⇒
⇒1 MULs, 1 ADD (一個乘法，一個加法)

(2)
⇒
⇒
⇒1 MULs, 1 ADD 

(3)
⇒
⇒2MULs, 4 ADDs 

(4)
⇒
⇒3MULs, 3 ADDs

複數的乘法
if   and  
⇒
令e為實數項，f為虛數項

(1) let  ; 
(2) let  ; 
⇒ ; 
⇒3MULs, 3～5 ADDs 
從這裡我們可以看出虛數的乘法量大致為實數乘法量的三倍。

参考

计算机逻辑