정리

• DFT는 N개의 복소 지수와의 내적이고, 그것을 행렬로 쓰면 $\mathbf X=W\mathbf x$이다. 정의대로의 계산과 FFT는 반올림 오차 안에서 같은 값을 낸다.
• 정의대로의 계산은 $N^2$, FFT는 $N\log N$에 비례해 늘어난다. 큰 N에서 이 차이가 측정 시간의 기울기로 보인다.
• FFT는 짝·홀 나누기와 회전 인자 $w_N^k$를 길이 1까지 되풀이한 것이다. 같은 알고리즘이라도 구현에 따라 시간은 크게 다르다.

보고서(과제 1)에는 자기 PC에서 잰 시간 그림과 표를 넣고, 큰 N에서의 기울기와 세 구현의 차이를 적는다.