Exercício 26.4. Escreva a recorrência para a transformada inversa rápida de Fourier (apenas para vetores de dimensão 2^k ).

Passo 1

O enunciado pede a recorrência de tempo da transformada inversa rápida de Fourier (iFFT) para vetores de comprimento 2^k. 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 N=2^k. Seja X=(X0,X1,dots,XN-1) o vetor de entrada no domínio de Fourier. Partimos em dois subproblemas de tamanho N/2:
X^(0)m = X2m, X^(1)m = X2m+1, m=0,dots,tfrac N2-1
Chamamos recursivamente
y = iFFTl(X^(0)r), z = iFFTl(X^(1)r)

Passo 3

Para combinar usamos a raiz da unidade inversa
omegaN = e^2pi i/N
e definimos para m=0,dots,tfrac N2-1
xm = ym + omegaN^m,zm, xm+tfrac N2 = ym - omegaN^m,zm
Após computar todos x0,dots,xN-1, aplica-se a normalização dividindo cada xj por N (ou, equivalentemente, multiplica-se por 1/N 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 Theta(N) trabalhos, e chamamos duas vezes o subproblema de tamanho N/2. Logo, se T(N) é o tempo para um vetor de tamanho N, temos
T(N) = 2,Tl(N/2r) + Theta(N),
com condição base T(1)=Theta(1).

Passo 5

Em termos de k, como N=2^k, podemos escrever
T(k)=2,T(k-1)+Theta(2^k),
com T(0)=Theta(1), o que implica T(N)=Theta(Nlog N).

Resposta

A recorrência de tempo da iFFT em vetores de dimensão 2^k é
T(1)=Theta(1), T(N)=2,Tl(N/2r)+Theta(N),
ou, em função de k,
T(0)=Theta(1), T(k)=2,T(k-1)+Theta(2^k)

Exercícios de Livros Relacionados