고속 푸리에 변환: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
Le Pied-bot~kowiki (토론 | 기여) 잔글 로봇이 더함: da:Fast Fourier Transform |
Wikier.bot (토론 | 기여) 잔글 봇이 동음이의 처리함: 소수 을 소수 (수론)로 연결 |
||
6번째 줄:
: <math>f_j = \sum_{k=0}^{n-1} x_k e^{-{2\pi i \over n} jk } \qquad j = 0,\dots,n-1</math>
이 식을 정의에 따라 계산하면 O(''n''<sup>2</sup>)의 연산이 필요하지만, FFT를 이용하면 O(''n'' log ''n'')의 연산만으로 가능하다. ''n''이 [[합성수]]일 경우 그 [[소인수분해]]를 이용하여 연산 횟수를 줄일 수는 있지만, FFT를 사용하면 ''n''이 [[소수 (수론)|소수]]일 경우에도 O(''n'' log ''n'')번의 연산 횟수를 보장한다.
== 쿨리-튜키 알고리즘 ==
| |||