Esclarecimento sobre FFT

Question

Eu sei que há algo de errado com o seguinte raciocínio, mas não tenho certeza o que é.

A FFT:

1. dadas dois polinômios

   A = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n

   e

   B = b_0 + b_1 x + b_2 x^2 + ... + b_n x^n

   Você pode calcular os coeficientes do produto

   AB = \sum _k = 0 ^ 2n ( \sum _ j = 0 ^ k (a_j b_{k-j}))x^k

   no tempo O(n log n ).

2. Assim, dado dois vetores (a_0, ..., a_n) e (b_0, ..., b_n) podemos calcular o v_i = \sum j = 0 ^ k ( a_j b_{k-j}) vector em tempo O(n log n) (incorporando os vectores em zeros.)

3. Diante do exposto, devemos ser capazes de calcular o produto escalar de A =(a_0, ..., a_n) e B =(b_0, ..., b_n) que é A.B = \sum_j=0 ^ n a_j b_j no tempo O(n log n) pelo pré-processamento de um dos vetores dizer B ser B' = (b_n, b_{n-1}, ..., b_1, b_0) então calcular a convolução como em 2. No O(n log n) Tempo.

Se o raciocínio acima é correta, então isso significa que podemos implementar Matrix multiplicação de duas matrizes nxn em tempo O(n^2 log n ) calculando o produto escalar em tempos O(n log n) tempo O(n).

No entanto, o melhor de tempo de execução para a multiplicação de matrizes que sabemos é sobre O(n^2.4) modo que este parece improvável que seja verdade, o que provavelmente meio de um dos passos 1,2, ou 3 está incorreto.

Answer 1

Existem entradas n^2 no produto, não n e por isso este algoritmo seria O(n^2 * n * log n) = O(n^3 log n).

E o melhor algoritmo para calcular produtos de ponto é O(n), não O(n log n). É por isso que o algoritmo ingênuo para multiplicação de matrizes é O(n^3). (É produtos n^2 ponto que pode ser feito em tempo O(n)).

Answer 2

Eu me pergunto por que isso é uma conquista que no passo 3 você pode calcular o produto escalar em O (n log n), como é bem sabido que produto de ponto pode ser calculado em O (n) tempo? etapa também 2 parece com o tempo linear em vez de O (n log n) passo?

Além disso, a conclusão sobre O (n ^ 2 log n) não segue logicamente. Você não pode tomar o O produto escalar (n) vezes resultando na matriz AB --- tanto quanto eu sei que você tem que tomar O (n ^ 2) dot produtos, levando a (por sua análise) O (n ^ 3 log n) que é inferior a ó padrão (n ^ 3). Isso é por causa de seu O estranho (n log n) dot resultado do produto.