다음 추론에 문제가 있음을 알고 있지만 확실하지 않습니다.FFT에 대한 설명
는 FFT :
두 다항식
A = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n
및
당신이 제품의 계수를 계산할 수 주어진B = b_0 + b_1 x + b_2 x^2 + ... + b_n x^n
AB = \sum _k = 0^2n (\sum _ j = 0^k (a_j b_{k-j}))x^k
O(n log n)
시간.그래서 주어진 두 벡터
(a_0, ..., a_n)
및(b_0, ..., b_n)
우리는 (제로의 벡터를 포함시켜.)O(n log n)
시간에 벡터v_i = \sum j = 0^k (a_j b_{k-j})
를 계산할 수위를 감안할 때, 우리의 내적을 계산 할 수 있어야한다
A =(a_0, ..., a_n)
및B =(b_0, ..., b_n)
인 벡터는B
이B' = (b_n, b_{n-1}, ..., b_1, b_0)
인 것으로 가정하고O(n log n)
시간에 2와 같이 컨볼 루션을 계산한다고 말하면서O(n log n)
에서A.B = \sum_j=0^n a_j b_j
입니다. 상기 추론이 정확하면
는, 그 우리 O(n log n)
시간 O(n)
배의 내적을 계산함으로써 O(n^2 log n)
시간 두 nxn
행렬 매트릭스 승산을 구현할 수 있다는 것을 의미한다.
그러나 우리가 알고있는 행렬 곱셈을위한 최적의 실행 시간은 약 O(n^2.4)
입니다. 따라서 이것이 사실 일 가능성은 희박합니다. 아마도 1,2,3 단계를 의미 할 것입니다.
B에서 B '로 변환하는 단계 (3)의 실행 시간은 얼마입니까? –