FFT 썸네일형 리스트형 고속 푸리에 변환(FFT)의 빠른 구현체 PS에서 고속 푸리에 변환(Fast Fourier Transform, FFT)을 쓰는 문제를 이따금씩 볼 수 있다. 컨볼루션은 주파수 영역에서 원소별 곱 연산(elementwise multiplication)으로 바뀌는 특성을 기반으로, FFT를 통해 \(O(n^2)\) 대신 \(O(n \lg n)\) 시간에 컨볼루션이 가능함을 이용하는 문제들이다. FFT는 크게 Cooley-Tukey, Split-Radix, Tangent의 세 가지 방법이 있다. Cooley-Tukey가 가장 간단하지만 비교적 느리고, Tangent가 가장 빠르지만 구현이 가장 복잡하다. 따라서 PS에서는 Cooley-Tukey를 쓰는 것이 일반적이다. 하지만 Cooley-Tukey는 구현 방법에 따라 실행 시간의 편차가 크게 수십 .. 더보기 이전 1 다음