고속 푸리에 변환(高速 푸리에 變換, 영어: Fast Fourier Transform, FFT)은 이산 푸리에 변환(영어: Discrete Fourier Transform, DFT)과 그 역변환을 빠르게 수행하는 효율적인 알고리즘이다. FFT는 디지털 신호 처리에서 편미분 방정식의 근을 구하는 알고리즘에 이르기까지 많은 분야에서 사용한다.
신호 이 복소수라고 가정할 때, DFT는 다음과 같이 정의한다.
이 식을 정의에 따라 계산하면 O(N 2)의 연산이 필요하지만, FFT를 이용하면 O(N log N)의 연산만으로 가능하다. N이 합성수일 경우 그 소인수 분해를 이용하여 연산 횟수를 줄일 수는 있지만, FFT를 사용하면 N이 소수일 경우에도 O(N log N)번의 연산 횟수를 보장한다.
을 회전자(Twiddle factor)라고 부른다. 1의 거듭제곱근(Root of unity), 단위근도 회전자의 다른 호칭이다. 이 회전자를 사용해 식(1)을 다시 정리하면,
회전자는 N에 관한 주기성으로 인해 다음과 같은 성질이 있음을 쉽게 알수있다.
- n:자연수
(예 1)