fft快速傅里叶变换

FFT（Fast Fourier Transformation）是一种快速计算离散傅里叶变换（DFT）的算法。它可以将一个信号从时域转换到频域，从而可以更好地分析信号的频率特性。FFT算法的时间复杂度为O(nlogn)，比朴素的DFT算法的时间复杂度O(n^2)要快得多。

下面是一个使用Python中的numpy库进行FFT变换的例子：

import numpy as np

# 生成一个正弦波信号
t = np.linspace(0, 1, 1000, endpoint=False)
x = np.sin(2*np.pi*10*t) + np.sin(2*np.pi*20*t)

# 对信号进行FFT变换
y = np.fft.fft(x)

# 计算频率
freq = np.fft.fftfreq(len(x), t[1]-t[0])

# 输出结果
print("频率为10Hz的分量的振幅为：", np.abs(y[np.where(freq==10)[0][0]])/len(x)*2)
print("频率为20Hz的分量的振幅为：", np.abs(y[np.where(freq==20)[0][0]])/len(x)*2)

输出结果为：

频率为10Hz的分量的振幅为： 0.9999999999999999
频率为20Hz的分量的振幅为： 0.9999999999999999

这说明我们生成的信号中包含10Hz和20Hz的两个正弦波分量，并且它们的振幅都为1。