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) 벡터를 계산할 수 있습니다 v_i = \sum j = 0 ^ k ( a_j b_{k-j}) 안에 O(n log n) 시간 (0에 벡터를 삽입하여)

3. 위의 내용을 고려할 때, 우리는 A =(a_0, ..., a_n) 그리고 B =(b_0, ..., b_n) 그게 A.B = \sum_j=0 ^ n a_j b_j 안에 O(n log n) 벡터 중 하나를 전처리하여 시간 B 되려고 B' = (b_n, b_{n-1}, ..., b_1, b_0) 그런 다음 2에서와 같이 컨볼 루션을 계산합니다 O(n log n) 시각.

위의 추론이 정확하다면, 우리는 두 가지의 행렬 곱셈을 구현할 수 있음을 의미합니다. nxn 매트릭스 O(n^2 log n ) 도트 제품을 계산하여 시간 O(n log n) 시각 O(n) 타임스.

그러나 우리가 아는 매트릭스 곱셈을위한 최고의 런타임은 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), 아니다 O(n log n). 그렇기 때문에 매트릭스 곱셈을위한 순진한 알고리즘이 O(n^3). (그것의 n^2 수행 할 수있는 도트 제품 O(n) 시각).

Answer 2

3 단계에서 O (n log n) 시간에서 도트 제품을 O (n) 시간에 계산할 수 있다는 것이 잘 알려져 있기 때문에 DOT 제품을 계산할 수 있다는 것이 왜 업적인지 궁금합니다. 또한 2 단계는 O (n log n) 단계 대신 선형 시간처럼 보입니까?

또한 o (n^2 log n)에 대한 결론은 논리적으로 따르지 않습니다. 당신은 도트 제품 O (n) 시간을 복용 할 수 없습니다. 3 log n) 표준 O보다 열등합니다 (n^3). 이것은 당신의 이상한 O (n log n) dot 제품 결과 때문입니다.