FFT 알고리즘, 왜 O(N²)이 O(N log N)으로 줄어들까

신호 처리의 심장, FFT를 다시 들여다보다

Jake VanderPlas가 2013년에 쓴 "Understanding the FFT Algorithm" 글이 다시 회자되고 있어요. 10년도 더 된 글이 왜 지금 또 읽히느냐면, FFT(고속 푸리에 변환)가 요즘 다시 중요해졌기 때문이에요. 오디오 AI, 음성 인식, 딥러닝 모델의 스펙트로그램 전처리, 심지어 그래프 뉴럴 네트워크의 스펙트럴 방법까지 전부 FFT 위에서 돌아가거든요. 이 글의 장점은 NumPy 코드로 한 줄씩 따라가면서 "왜 O(N²)이 O(N log N)으로 줄어드는가"를 직접 눈으로 확인할 수 있다는 거예요.

먼저, 푸리에 변환이 뭐냐면

푸리에 변환을 아주 쉽게 말하면, "시간에 따라 변하는 신호를 주파수 성분들의 합으로 쪼개는 작업"이에요. 예를 들어 피아노 화음 소리를 녹음하면 공기의 압력이 시간에 따라 복잡하게 흔들리는 파형이 잡히잖아요. 이걸 푸리에 변환에 넣으면 "아, 도(C4) + 미(E4) + 솔(G4)가 섞여 있네요" 하고 주파수별 성분을 뽑아줘요. 이미지 압축(JPEG), 음원 압축(MP3), 통신, 의료 영상(MRI) 전부 이 변환 위에 서 있어요.

이산 신호(샘플링된 디지털 신호)에 적용하는 걸 DFT(이산 푸리에 변환)라고 해요. 수식으로 쓰면 각 주파수 k에 대해 X[k] = Σ x[n] · e^(-2πi·kn/N)을 계산하는 건데요. 문제는 이걸 직접 계산하면 N개 신호를 N개 주파수로 변환하는 데 N² 번 연산이 필요해요. N이 백만이면 1조 번이에요. 현실적으로 안 돼요.

FFT의 핵심 아이디어: 분할과 재사용

1965년 Cooley와 Tukey가 발표한 Cooley-Tukey 알고리즘의 핵심은 간단해요. "N개짜리 DFT를 짝수 인덱스 N/2개짜리 DFT 하나랑, 홀수 인덱스 N/2개짜리 DFT 하나로 쪼개자"는 거예요. 이게 왜 되냐면, 지수 함수 e^(-2πi·kn/N)이 주기성과 대칭성을 가지고 있어서, 짝수·홀수로 나눈 뒤 다시 합칠 때 추가 연산이 N번이면 끝나거든요.

점화식으로 쓰면 T(N) = 2·T(N/2) + O(N)이 되고, 이건 머지 정렬과 똑같은 구조예요. 그래서 O(N log N)이 나와요. N이 백만일 때 1조 번이 2천만 번으로 줄어요. 약 5만 배 빨라지는 거예요. 이 한 번의 수학적 통찰이 현대 디지털 신호 처리 전체를 가능하게 만들었다고 해도 과언이 아니에요.

VanderPlas 글의 매력

이 글이 특별한 이유는 세 단계로 코드를 보여준다는 거예요. 먼저 순진한 DFT를 NumPy로 작성해요. 이중 루프 대신 행렬곱 한 줄로 쓰는데, 이것만 해도 벡터화의 위력을 보여줘요. 그다음 재귀적 FFT를 구현해요. 짝수·홀수로 나누고 자기 자신을 호출하는 10줄짜리 코드인데, 이게 순진한 DFT보다 수백 배 빨라져요. 마지막으로 벡터화된 FFT를 보여줘요. 재귀 대신 버터플라이 연산을 행렬 형태로 펼쳐서, 파이썬 함수 호출 오버헤드를 없애버려요.

이 과정을 따라가면 "아, FFT는 마법이 아니라 분할 정복이구나" 하는 감각이 확 와요. 그리고 왜 입력 길이가 2의 거듭제곱일 때 가장 빠른지(N/2로 계속 쪼개져야 하니까), 왜 라이브러리들이 패딩(padding)을 하는지도 자연스럽게 이해되고요.

업계 맥락: FFT가 여전히 중요한 이유

요즘은 다들 numpy.fft, scipy.fft, torch.fft를 그냥 가져다 쓰는데, 내부적으로는 FFTW(서방 세계에서 가장 빠른 푸리에 변환 라이브러리)나 Intel MKL, NVIDIA cuFFT가 돌아가요. 이들은 Cooley-Tukey 외에도 Prime Factor Algorithm, Bluestein's Algorithm, Rader's Algorithm 같은 변종을 섞어서 어떤 N이든 빠르게 처리해요.

AI 관점에서 보면, 음성 AI(Whisper, Wav2Vec)는 입력을 mel-spectrogram으로 바꾸는 전처리에서 FFT를 수만 번 돌려요. 확산 모델(diffusion)에서도 주파수 공간 분석이 쓰이고, FNO(Fourier Neural Operator) 같은 모델은 아예 아키텍처 한가운데에 FFT를 박아놨어요. 하드웨어 수준에서도 최근 NVIDIA의 Tensor Core가 FFT를 가속하는 방향으로 발전하고 있고요.

한국 개발자에게 주는 시사점

주니어 입장에선 "FFT는 신호처리 전공자나 쓰는 거 아냐?" 싶을 수 있는데, 오디오·영상·시계열·AI 전처리를 건드리는 순간 바로 만나게 돼요. 특히 요즘 음성 LLM, 음악 생성 모델, 실시간 자막 시스템 같은 프로젝트가 쏟아지고 있는데, 그 뿌리는 결국 FFT예요. 구현까지 직접 할 일은 드물지만, 내부 동작을 이해하면 디버깅과 파라미터 튜닝이 훨씬 쉬워져요. 윈도우 함수(Hann, Hamming)를 왜 곱하는지, zero-padding을 왜 하는지, STFT의 hop size는 왜 중요한지가 한번에 이해되거든요.

한 번쯤 이 글을 따라 주피터 노트북에서 15줄짜리 FFT를 직접 짜보세요. 한 시간이면 끝나고, 평생 쓸 감각이 남아요.