고속 푸리에 변환(FFT)의 원리와 다항식 곱셈의 효율적 처리
다항식 $A(x) = \sum_{i=0}^{n} a_i x^i$와 $B(x) = \sum_{i=0}^{m} b_i x^i$가 주어졌을 때, 두 다항식의 곱인 $C(x) = A(x)B(x)$를 구하는 문제를 생각해 봅시다. 일반적인 계수 중심의 곱셈 방식(Convolution)은 $O(nm)$의 시간 복잡도를 가집니다. 하지만 고속 푸리에 변환(FFT)을 이용하면 이를 $O(N \log N)$ 수준으로 최적화할 수 있습니다.
점-값 표현법 (Point-V ...
10월 2일 17:47에 게시됨