토픽 48 / 82

FFT (Fast Fourier Transform)

이산 푸리에 변환(DFT)을 O(n log n) 시간에 계산하는 고속 알고리즘으로, 분할 정복을 활용하여 시간 영역 신호를 주파수 영역으로 변환하며 다항식 곱셈, 신호 처리에 널리 사용

목적: 고속 푸리에 변환, 주파수 분석, 다항식 곱셈, 신호 처리

특징: O(n log n) 복잡도, 분할 정복, 복소수 연산, 재귀/반복 구현

DFT: X(k) = Σ x(n)e^(-i2πkn/N), O(n²) 시간 → FFT는 O(n log n)

Cooley-Tukey 알고리즘: 가장 일반적인 FFT, 짝수/홀수 인덱스로 분할 → 재귀 → 병합

동작: ① N개 신호를 N/2 짝수/홀수로 분할 → ② 재귀적으로 FFT 계산 → ③ 회전 인수(Twiddle Factor) 적용하여 병합

회전 인수(Twiddle Factor): W_N^k = e^(-i2πk/N), 복소 단위근

시간 복잡도: O(n log n), n = 2^k (2의 거듭제곱 가정)

공간 복잡도: O(n)

IFFT(Inverse FFT): FFT와 거의 동일, 회전 인수 부호 반대, 결과를 N으로 나눔

장점: 매우 빠름(O(n log n)), 다양한 응용, 표준 알고리즘

단점: 복소수 연산, 수치 오차, 2의 거듭제곱 선호

적용사례: 다항식 곱셈, 신호 처리(오디오/이미지), 데이터 압축(JPEG/MP3), 스펙트럼 분석, 빅 인티저 곱셈

비교: FFT(O(n log n)) vs DFT(O(n²)) vs NTT(정수/모듈로)

연관: DFT, 푸리에 변환, 신호 처리, 다항식 곱셈, 복소수