Khác biệt giữa bản sửa đổi của “Biến đổi Fourier nhanh”

:<math>X_k = \sum_{n=0}^{N-1} x_n e^{-{i 2\pi k \frac{n}{N}}}\qquad k = 0,\dots,N-1.</math>

Tính trực tiếp từ định nghĩa trên đòi hỏi O(''N²'') phép tính: có ''N'' số ''X_k'' cần tính, để tính mỗi số cần tính một tổng ''N'' số hạng. Một FFT là một phương pháp để tính cùng kết quả đó trong O(''N'' log ''N'') phép tính.

 

==Các thuật toán==