Exercício 26.4. Escreva a recorrência para a transformada inversa rápida de Fourier (apenas para vetores de dimensão
).
Passo 1
O enunciado pede a recorrência de tempo da transformada inversa rápida de Fourier (iFFT) para vetores de comprimento
. O método é divide-and-conquer, idêntico ao FFT exceto pelo sinal e pelo fator de normalização, e vamos precisar dividir o vetor em índices pares e ímpares e depois combinar com as raízes da unidade.
Passo 2
Definimos
. Seja
o vetor de entrada no domínio de Fourier. Partimos em dois subproblemas de tamanho
:
Chamamos recursivamente
Passo 3
Para combinar usamos a raiz da unidade inversa
e definimos para
Após computar todos
, aplica-se a normalização dividindo cada
por
(ou, equivalentemente, multiplica-se por
no topo da recusão).
Passo 4
Contando operações de combinação (somas, subtrações e multiplicações por raízes), em cada nível de recursão fazemos
trabalhos, e chamamos duas vezes o subproblema de tamanho
. Logo, se
é o tempo para um vetor de tamanho
, temos
com condição base
.
Passo 5
Em termos de
, como
, podemos escrever
com
, o que implica
.
Resposta
A recorrência de tempo da iFFT em vetores de dimensão
é
ou, em função de
,