# FFT卷積的速度比較
相關文檔: [_頻域信號處理_](frequency_process.html)
直接卷積的復雜度為O(N*N),FFT的復雜度為O(N*log(N)),此程序分別計算直接卷積和快速卷積的耗時曲線。請注意Y軸為每點的平均運算時間。

```
# -*- coding: utf-8 -*-
import numpy as np
import timeit
def fft_convolve(a,b):
n = len(a)+len(b)-1
N = 2**(int(np.log2(n))+1)
A = np.fft.fft(a, N)
B = np.fft.fft(b, N)
return np.fft.ifft(A*B)[:n]
if __name__ == "__main__":
from pylab import *
n_list = []
t1_list = []
t2_list = []
for n in xrange(4, 14):
N = 2**n
count = 10000**2 / N**2
if count > 10000: count = 10000
setup = """
import numpy as np
from __main__ import fft_convolve
a = np.random.rand(%s)
b = np.random.rand(%s)
""" % (N, N)
t1 = timeit.timeit("np.convolve(a,b)", setup, number=count)
t2 = timeit.timeit("fft_convolve(a,b)", setup, number=count)
t1_list.append(t1*1000/count/N)
t2_list.append(t2*1000/count/N)
n_list.append(N)
figure(figsize=(8,4))
plot(n_list, t1_list, label=u"直接卷積")
plot(n_list, t2_list, label=u"FFT卷積")
legend()
title(u"卷積的計算時間")
ylabel(u"計算時間(ms/point)")
xlabel(u"長度")
xlim(min(n_list),max(n_list))
show()
```
- 用Python做科學計算
- 軟件包的安裝和介紹
- NumPy-快速處理數據
- SciPy-數值計算庫
- matplotlib-繪制精美的圖表
- Traits-為Python添加類型定義
- TraitsUI-輕松制作用戶界面
- Chaco-交互式圖表
- TVTK-三維可視化數據
- Mayavi-更方便的可視化
- Visual-制作3D演示動畫
- OpenCV-圖像處理和計算機視覺
- Traits使用手冊
- 定義Traits
- Trait事件處理
- 設計自己的Trait編輯器
- Visual使用手冊
- 場景窗口
- 聲音的輸入輸出
- 數字信號系統
- FFT演示程序
- 頻域信號處理
- Ctypes和NumPy
- 自適應濾波器和NLMS模擬
- 單擺和雙擺模擬
- 分形與混沌
- 關于本書的編寫
- 最近更新
- 源程序集
- 三角波的FFT演示
- 在traitsUI中使用的matplotlib控件
- CSV文件數據圖形化工具
- NLMS算法的模擬測試
- 三維標量場觀察器
- 頻譜泄漏和hann窗
- FFT卷積的速度比較
- 二次均衡器設計
- 單擺擺動周期的計算
- 雙擺系統的動畫模擬
- 繪制Mandelbrot集合
- 迭代函數系統的分形
- 繪制L-System的分形圖