FFT에 대한 설명

Question

다음 추론에 문제가 있음을 알고 있지만 확실하지 않습니다.

는 FFT :

1. 두 다항식

   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) 시간.

2. 그래서 주어진 두 벡터 (a_0, ..., a_n) 및 (b_0, ..., b_n) 우리는 (제로의 벡터를 포함시켜.) O(n log n) 시간에 벡터 v_i = \sum j = 0^k (a_j b_{k-j})를 계산할 수

3. 위를 감안할 때, 우리의 내적을 계산 할 수 있어야한다 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 단계를 의미 할 것입니다.

Answer 1

제품에 n^2 항목이 있으며 n이 아니므로 O(n^2 * n * log n) = O(n^3 log n)이됩니다.

그리고 내적을 계산하는 데 가장 적합한 알고리즘은 O(n log n)이 아니라 O(n)입니다. 이것이 행렬 곱셈에 대한 순진 알고리즘이 O(n^3) 인 이유입니다. (O(n) 시간에 완료 할 수있는 제품은 n^2입니다.)

Answer 2

3 단계에서 점 제품을 O (n) 시간에 계산할 수 있다는 것이 잘 알려져 있으므로 O (n log n) 시간에 내적을 계산할 수 있다는 성과가 궁금합니다. 또한 2 단계는 O (n log n) 단계 대신 선형 시간처럼 보입니까?

또한 O (n^2 log n)에 대한 결론은 논리적으로 따르지 않습니다. O (n^2) 점의 제품을 가져 와서 (분석 당) O (n^2) 점을 가져야한다는 것을 안다면, 3 로그 n) 표준 O (n^3)보다 열등합니다. 이것은 이상한 O (n log n) 내적 결과 때문입니다.