重畳加算法
したがって重畳加算法の計算量はほぼ O ( N x log 2  N ) {\displaystyle O(N_{x}\log _{2}{N})} でスケールし、他方、普通の巡回畳み込みの計算量はほぼ O ( N x log 2  N x ) {\displaystyle O(N_{x}\log _{2}{N_{x}})} である。(訳注: N > N x {\displaystyle N>N_{x}} なので重畳加算法の方が計算量が多い事になってしまう。2つの計算量は要検証) しかしながら、この種の推計は複素数乗算の計算量だけ考慮しており、アルゴリズムに関わる他の処理は度外視している。各アルゴリズムに要する計算時間の直接測定こそ、より大きな関心事である。 図2に、式1による標準的な巡回畳み込みの計算時間と、アルゴリズム 2の形の重畳加算法による同様な畳み込みの計算時間の比を示す; 縦軸は信号長 N x {\displaystyle N_{x}} の対数表示、横軸はフィルタ長 N h = M {\displaystyle N_{h}=M} の対数表示で、計算時間の比を等高線で示している。両アルゴリズムはMatlabで実装した。青い太線は、重畳加算法の方が標準巡回畳み込みより速い(比>1)領域の境界線である。このケースでは重畳加算法は標準的手法より最大約3倍高速だった。