Isso usa o algoritmo de transformação rápida de Fourier (FFT).
Para multiplicar dois polinômios em tempo O (nlogn) .
Neste artigo, descreverei a multiplicação de dois polinômios em tempo O (nlogn) . Isso usa o algoritmo de transformação rápida de Fourier (FFT).
Rivest descreve
O livro "Introdução aos Algoritmos" de Cormen, Leiserson e Rivest descreve a multiplicação de dois polinômios no tempo O (nlogn). Aqui, descreverei uma variante do método que eles usaram.
Em primeiro lugar, uma revisão de alguns princípios básicos:
1. A (x) = a_0 + a_1 (x) + a_2 (x ^ 2) +..... + a_ (n-1) (x ^ (n-1)) é um polinômio de grau n-1.
2. Multiplicação dos polinômios A (x) e B (x), isto é, C (x) = A (x) B (x) leva tempo O (n ^ 2).
3. Encontrar A (p) é substituir p no lugar de x no polinômio: A (p) = a_0 + a_1 (p ^ 2) +..... + a_ (n-1) (p ^ (n -1)). Isso pela Regra de Horner é: A (p) = a_0 + p (a_1 + p (a_2 +..... + p (a_ (n-1))...). Isso leva O (n).
4. Existem dois tipos de representações para polinômios:
Forma do coeficiente: (a_0, a_1, a_2,....., a_ (n-1)). Forma de valor pontual: {(x_0, y_0), (x_1, y_1),... (x_n-1, y_n-1)}, onde y (x_i) = A (x_i).
Formulários leva
5. A conversão das formas de coeficiente para valor de ponto leva O (n ^ 2) mesmo usando a Regra de Horner porque o valor de A (x) deve ser encontrado em n pontos.
6. A enésima raiz complexa da unidade é um número complexo w * tal que w * ^ n = 1.
Raiz principal enésima
7. As enésimas raízes da unidade são: w ^ 0, w ^ 1, w ^ 2,...., w ^ n-1. w = e ^ (2 * pi * i / n) é chamado de enésima raiz principal da unidade e todas as n raízes são potências deste w.
8. Periodicidade: w ^ (k + n) = w ^ k.
Com este pano de fundo podemos começar.
Cobrir de volta
Para multiplicar dois polinômios A (x) e B (x) dados em formas coeficientes, primeiro os convertemos em formas de valor de ponto. A multiplicação na forma de valor de ponto assume O (n). Em seguida, voltamos à forma coeficiente. No entanto, a conversão de coeficiente para valor de ponto leva O (n ^ 2), como dito em 5. Mas, ao escolher os pontos x_0, x_1,..... x_ (n-1) com cuidado, podemos conseguir isso em O (nlogn).
Esses pontos que vamos escolher serão as enésimas raízes da unidade. Isso é o que é Transformada Discreta de Fourier (DFT).
Termos ímpares
O livro "Introdução aos Algoritmos" de Cormen, Leiserson e Rivest descreve a multiplicação de dois polinômios no tempo O (nlogn).
Agora, A (x) = a_0 + a_1 (x) + a_2 (x ^ 2) +..... + a_ (n-1) (x ^ (n-1)). Isso pode ser dividido em dois polinômios: o primeiro contendo os primeiros n / 2 termos e o segundo contendo os segundos n / 2 termos. O livro "Introdução aos algoritmos" descreve a divisão como termos pares e ímpares. Aqui, podemos chegar ao mesmo resultado, mas de uma maneira ligeiramente diferente.
A (x) = A_0 (x) + x ^ (n / 2) A_1 (x) - - - - - -> (1).
Agora, ao substituir w no lugar de x, vemos que x ^ (n / 2) na equação (1) torna-se (x ^ (n / 2)) = (w ^ (n / 2)) = +1, -1 ou seja, as duas raízes da unidade.
Podemos separar as amostras em duas amostras de termos pares e ímpares. Todo o DFT de n pontos agora se tornou dois DFTs de n / 2 pontos.
Esses dois DFTs de n / 2 pontos podem ser divididos em dois DFTs de n / 4 pontos e assim por diante. Portanto, a complexidade do algoritmo resultante é O (nlogn).
Na abordagem descrita em "Introdução aos Algoritmos", as amostras são divididas em amostras pares e ímpares para obter as amostras da primeira e segunda metade, exatamente o oposto do que temos obtido atualmente.
O algoritmo recrursivo pode ser dado como:
Retornar
Recursive_FFT (a) { n <- comprimento (a) se (n = 1) retornar a
w <- e ^ (2 * pi * i / n) a [0] <- (a_0, a_1,......, a_ (n / 2-1)) a [1] <- (a_n / 2, a_ (n / 2 + 1),........, a_ (n-1))
y [0] <- Recursive_FFT (a [o]) y [1] <- Recursive_FFT (a [1])
para k <- 0 a n / 2 -1 comece y_2k <- y_k [0] + y_k [1] y_2k + 1 <- y_k [0] - y_k [1] fim retorno y }
A equação recorrente é: T (n) = 2T (n / 2) + O (n), se tomarmos O (n) para cada chamada recursiva. Portanto, T (n) = O (nlogn).
Faça multiplicação
Depois de obter a forma de valor de ponto, podemos realizar a multiplicação no tempo O (n).
A conversão do valor do ponto para a forma coeficiente pode ser feita de forma semelhante em O (nlogn). Isso é chamado de interpolação.
Todo o processo de multiplicação, portanto, leva O (nlogn).
