고속 푸리에 변환(FFT) 설명: Cooley-Tukey 알고리즘

이 글에서는 고속 푸리에 변환(FFT) 알고리즘, 특히 Cooley-Tukey 알고리즘에 대해 자세히 설명합니다. 먼저 이산 푸리에 변환(DFT)의 정의를 제시하고, 단순한 O(n^2) 시간 복잡도를 지적합니다. 그런 다음 Cooley-Tukey 알고리즘을 자세히 유도하여 DFT를 더 작은 DFT로 분해함으로써 계산량을 줄이고, 입력 길이가 2^n인 경우 O(n log n)으로 감소시키는 것을 보여줍니다. 알고리즘의 동작을 시각적으로 보여주는 대화형 시각화도 포함되어 있습니다. 또한 FFT와 DFT를 혼동하는 일반적인 오용에 대해서도 수정하고, FFT는 변환 자체가 아니라 알고리즘을 가리킨다는 것을 명확히 합니다.