우함수기함수
-
FFT가 빠른 이유Math♾️/Fourier Analysis 2023. 6. 22. 15:58
다항식 A(x)와 B(x)의 곱을 C(x)라고 하자. 이때 다항식 C(x)의 각 항의 계수들은 다음과 같이 각 항을 차례대로 곱하는 분배법칙을 통해서 구할 수 있다. 다항식 간의 곱 연산 시 계산되는 요소는 각 항의 계수이므로 다음과 같이 다항식의 각 항의 계수들만 배열의 형태로 나타내는 방법을 Coefficient Representation이라고 한다. Coefficient Representation을 이용해 각 항을 곱해나가며 계산을 할 경우 A(x)의 각 항은 B(x)의 모든 항과 한 번씩 곱연산을 수행해야 한다. 따라서 A(x), B(x)를 최고차항이 d라고 하면 A(x)의 하나의 항당 B(x)의 모든 d개의 항에 대해서 곱연산을 하며 이를 A(x)의 모든 d개 항에 실시하므로 기본적으로 총 d*..