Como visto anteriormente, a Transformada Discreta de Fourier é dada por:
 

(1)

onde

A transformada inversa é dada por:
 

(2)

Em ambas as equações , x(n) e X(k) podem ser complexos. As equações (1) e (2) diferem somente pelo sinal da exponencial e por um fator de escala. Assim, os procedimentos computacionais de (1) se aplicam, com algumas modificações, a (2).

Para mostrar a importância de esquemas computacionais eficientes, é instrutivo avaliar diretamente as equações da transformada discreta.

Como x(n) pode ser complexo, podemos escrever
 

(3)

Da equação (3) observa-se que, para cada valor de k, o cálculo direto de X(k) requer
                 4N multiplicações reais e
                (4N-2) adições reais.

Como X(k) deve ser calculado para N valores diferentes de k, o cálculo direto da Transformada Discreta de Fourier de uma sequência x(n) requer
                 4N² multiplicações reais e
                 N(4N-2) adições reais

Ou, alternativamente,
                 N² multiplicações complexas e
                 N(N-1) adições complexas.

Além das somas e multiplicações, a implementação da DFT em um computador digital requer que os termos da sequência x(n) e os valores dos coeficientes WN possam ser armazenados e recuperados. Como a quantidade de informação armazenada em algoritmos numéricos é geralmente proporcional ao número de operações aritméticas, é aceitável que uma medida significativa da complexidade, ou, do tempo requerido para se implementar um algoritmo computacional seja o número de adições e multiplicações envolvidas.

Então, para a computação direta da Transformada Discreta de Fourier, uma medida conveniente da eficiência da computação é o fato de são requeridas
                 4N² multiplicações reais e
                 N(4N-2) adições reais.

Como o número de operações e, consequentemente, o tempo de computação é aproximadamente proporcional a N², fica evidente que o número de operações aritméticas se torna muito extenso para valores grandes de N. Por isso, algoritmos computacionais que reduzem o número de adições e multiplicações são de considerável interesse.

Algumas propriedades de WN são importantes para aumentar a eficiência da computação da TFD. São elas:
 

1)
2)

Por exemplo, usando a primeira propriedade, pode-se agrupar termos na equação (3) como abaixo:
 

Por esse método, o número de multiplicações pode ser reduzido por, aproximadamente, um fator 2.

Além disso, o fato de as funções seno e cosseno assumirem valor 0 ou 1 para certos valores de kn faz com que certas multiplicações sejam eliminadas.

No entanto, número de operações ainda é aproximadamente proporcional a N². Felizmente, a segunda propriedade pode ser utilizada para obtenção de mais reduções no número de operações.

Algoritmos computacionais que exploram tanto a simetria quanto a periodicidade das quantidades WN foram descobertos bem antes da era da computação digital de alta velocidade. Naquela época, qualquer procedimento que reduzisse a computação manual por um fator 2 era bem vindo. Runge, e mais tarde Lancsos e Danielson, descreveram algoritmos para os quais o número de operações era proporcional a N log N, ao invés de N². No entanto, estes eram indiferentes aos pequenos valores de N plausíveis para cálculo manual.

A possibilidade de grande redução nos cálculos só apareceu em 1965, quando Cooley e Tukey publicaram um algoritmo para cálculo da DFT que só poderia ser aplicado quando N fosse um número composto, ou seja, produto de 2 ou mais inteiros. A publicação de tal artigo resultou em uma grande aplicação da Transformada Discreta de Fourier a processamento de sinais, e como resultado foram descobertos vários algoritmos computacionais que ficaram conhecidos como algoritmos FFT (Fast Fourier Transform).

O princípio fundamental desses algoritmos é decompor sucessivamente a computação da transformada discreta de uma sequência de tamanho N em Transformadas Discretas de Fourier menores. A maneira na qual tal princípio é implementado leva a uma variedade de algoritmos diferentes, todos com comparáveis melhoras na velocidade de computação.

Duas classes básicas de algoritmos FFT são interessantes.
A primeira, chamada decimação no tempo ("decimation-in-time"), recebe tal denominação devido ao fato de que no processo de cálculo, a sequência x(n) é decomposta sucessivamente em subsequências menores.

Na segunda classe de algoritmos, a sequência de coeficientes da Transformada Discreta de Fourier, X(k), é decomposta em subsequências menores, e logo recebe a denominação de decimação na frequência ("decimation-in-frequency").

Serão consideraremos aqui alguns algoritmos para cálculo da DFT.

Começaremos com a discussão do algoritmo de Goertzel, no qual o número de operações é proporcional a N², porém com constante de proporcionalidade menor do que no método direto.