FFT 이란?

FFT(Fast Fourier Transform)는 DFT를 고속으로 연산하는 알고리즘이다.

 

n개의 데이터를 모두 DFT를 하려면 n x n 번의 연산이 필요하다. 1,000개의 데이터를 DFT를 하려면 1,000,000번의 연산이 필요하다.

 

FFT 알고리즘을 사용하면 n x log(n) 번의 연산이 필요하다. 1,000개의 데이터를 FFT 하면 3,000번의 연산이 필요하다. FFT가 1/333 배로 연산량이 준다.

 

위에서 말한 연산은 복소수 곱셈 연산이다.

 

FFT로 가장 많이 사용하는 알고리즘은 Cooley–Tukey 알고리즘이다.

 

☞ FFT 코드