[23 하계 모각코] 2회차 FFT알고리즘

배연우·2023년 7월 14일

개인모각코

목록 보기

1/5

FFT 알고리즘을 공부해야 하는 이유는 어떻게 해야 다항식의 곱셈의 연산의 속도를 더 줄일 수 있을지를 배우기 위해서 배우는 것이다. 이 알고리즘은 매우 흥미로운데, 복소수와 간단한 선형대수학을 이용한다.

연산 절차

이 책에서는 다항식의 연산을 세가지로 나누어서 진행한다.
1. 두 다항식의 n개의 해를 구한다.
2. 두 다항식의 해를 곱해서 곱해질 다항식의 해를 n개 구해낸다.
3. 새로운 해의 개수가 n개 이므로, 이 식을 이용하면 단 하나의 새로운 다항식(정답)을 구해낼 수 있다.

이런 식으로 해야 nlogn의 시간복잡도를 가질 수 있다.

1번: Evaluation

트릭

n개의 해를 구해야 하고, 해를 구하는 데에는 n-1개의 항에 값을 넣어야 하기에 $O(n)$ 의 시간 복잡도가 걸린다. 즉 1단계는 $O(n^2)$ 의 시간 복잡도가 걸리게 된다. 어떻게 해야 더 빠르게 구할 수 있을까?

여기 트릭이 있다:
1. 만약 2차식의 두 해가 1과 -1이라면 어떻게 될까? 결론부터 말하자면 계산을 한번만 수행해도 되게 할 수 있다.

이게 가능해지는 이유는 1과 -1인 경우 홀수 차수의 경우 값이 반대가 되고, 짝수 차수의 경우 값이 똑같기 때문에 홀수 차수, 짝수 차수들을 따로 연산하고 홀수 차수에만 -1 을 곱해주면 한 연산으로 2개의 해를 구할 수 있기 때문이다.

그러나 문제가 있다. 위 트릭의 경우, 첫번째 level에서만 가능하다. 그렇기에 이 책에서 해결책으로 제시한 것은 복소수이다.

복소수

왜 복소수만 있으면 해결이 되는 걸까? 그걸 알기 위해선 복소평면과 복소수의 곱에 대해서 잘 알아야 한다.

우선 복소평면은 간단하다. x축에 실수, y축에 허수를 두는 거다.
예를 들어 $2 + i$ 는 이렇게 표기한다.

여기서 우리는 xy좌표계가 아닌 극좌표계를 사용할 것이다. 극좌표계는 $(x, y)$ 좌표축 대신 $(r, \theta)$ 좌표축을 사용하는 방식이다.

자 그리고 복소평면에서 곱을 보자.
$p_1 = (r_1, \theta_1), p_2 = (r_2, \theta_2)$ 인 경우에, 이 둘의 곱은 다음과 같다: $(r_1 \times r_2, \theta_1 + \theta_2)$
이 식을 보면 알 수 있듯, $r_1, r_2$ 가 1이면 곱해진 $r$ 의 값도 1일 것이고, $\theta$ 는 더해지고, $2\pi$ 만큼 회전하면 다시 0이 되는 원리 때문에, n개의 해를 구해야 하는 경우, n제곱해서 1이 되는 복소수들이 적절한 해가 된다. (+: 서로 양 극단에 있는 해의 경우, -1을 곱한 것으로 생각하고, 연산을 줄일 수 있다.)

결과적으로는 evaluation을 $O(2^n)$ 의 시간복잡도에서 $T(n) = 2T(\frac{n}{2}) + O(n) = O(nlogn)$ 의 시간복잡도를 가지게 된다는 것을 알 수 있다.

3번: interpolation

만약 3번 역시 $O(nlogn)$ 의 시간을 가지게 된다면 다항식의 곱 연산은 실제로 $O(nlogn)$ 의 시간복잡도를 가진다 말할 수 있다. 하지만 진짜로 그런 것일까?

행렬을 통한 증명

간단히 설명이 가능하다.
자 우리 $y = Ax$ ( $y$ = n개의 해, $A$ = $x_0 ... x_{n-1}$ 의 row를 n개 쌓아놓는 행렬, $x$ = 복소수 행렬$ 으로 evaulation을 할 수 있다. 그리고 이 경우, $A$ 는 역행렬을 가지고 있으므로, 이렇게 표현이 가능하다. $A^{-1}y = x$ 즉 interpolation 역시 $O(nlogn)$ 의 시간복잡도를 가지게 된다.