계산량과 로그

핵심 질문

계산을 반씩 나누면 왜 훨씬 빨라질까?

교과서 설명

어떤 알고리즘이 입력 크기 $N$에 따라 얼마나 많은 계산을 하는지 대략 나타낼 때 $O(\cdot)$ 표기를 쓴다.

DFT를 그대로 계산하면 모든 출력 $k$마다 모든 입력 $n$을 확인한다. 그래서 대략 다음만큼 계산한다.

이것을 $O(N^2)$이라고 쓴다.

FFT는 문제를 반씩 나누어 다시 합친다. $N$을 계속 반으로 나누면 몇 번 만에 $1$이 되는지 나타내는 수가 $\log_2 N$이다.

위 과정은 $3$번 나누었으므로

이다. FFT의 계산량은 대략 다음처럼 줄어든다.

여기서 $\log N$은 보통 $\log_2 N$처럼 “몇 번 반으로 나눌 수 있는가”라는 뜻으로 생각해도 충분하다.

Big-O와 점화식으로 보는 차이

$O(\cdot)$ 표기는 정확한 실행 시간을 말하는 것이 아니라, 입력 크기가 커질 때 지배적으로 커지는 항을 나타내는 표기다. 예를 들어

은 $N$이 커질수록 $N^2$ 항이 가장 중요하므로 $O(N^2)$이라고 쓴다.

DFT를 직접 계산하면 출력 $X[k]$가 $N$개 있고, 각 출력마다 입력 $x[n]$을 $N$개 모두 더한다.

반면 FFT는 길이 $N$ 문제를 길이 $N/2$ 문제 두 개로 나누고, 마지막에 $N$개 정도의 값을 합친다. 이를 점화식으로 쓰면

재귀 단계별로 보면 더 분명하다. $r$번째 단계에는 작은 문제가 $2^r$개 있고, 각각의 크기는 $\frac{N}{2^r}$이다. 그 단계에서 합치는 총량은 대략

으로 일정하다.

한 단계의 총 합치는 비용은 $N$, 단계 수는 $\log_2N$이므로 전체는

이 된다. 여기서 중요한 것은 “반으로 나누기”만으로 충분하지 않다는 점이다. 작은 문제의 결과를 다시 쓸 수 있는 단위원근의 대칭이 있어야 이 점화식이 성립한다.

직관 비유

토너먼트 대진표를 생각하자. 16명이 참가하면 한 라운드가 끝날 때마다 남은 사람 수가 16명, 8명, 4명, 2명, 1명으로 반씩 줄어든다. 우승자가 나오기까지 필요한 라운드 수가 $\log_2 16=4$이고, 로그는 이렇게 “몇 번 반으로 줄이면 하나가 되는가”를 세는 말이다.

예제

$N=16$이면 반으로 나누는 과정은 다음과 같다.

따라서

그냥 DFT 계산량과 FFT식 계산량을 거칠게 비교하면

이고,

이다. 실제 알고리즘에는 숨은 상수가 있지만, 입력이 커질수록 차이가 빠르게 벌어진다.

손풀이 체크

1. $32$를 계속 반으로 나누면 몇 번 만에 $1$이 될까?

   답 보기

   $5$번

2. $\log_2 8$은?

   답 보기

   $3$

3. $N=8$일 때 $N^2$과 $N\log_2N$은 각각 얼마일까?

   답 보기

   $64$와 $24$

다음으로 이어지는 생각

FFT가 빠른 이유는 단순히 반으로 나누기 때문만은 아니다. 단위원 위 회전값들이 서로 짝을 이루는 성질도 함께 사용한다.