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

n
→‎Định nghĩa và tốc độ: clean up, replaced: . → . using AWB
n (→‎Định nghĩa và tốc độ: clean up, replaced: . → . using AWB)
 
==Định nghĩa và tốc độ==
Giả sử ''x<sub>0</sub>, x<sub>1</sub>, ..., x<sub>n</sub>'' là các [[số phức]]. DFT được định nghĩa bởi công thức sau:
:<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<sup>2</sup>'') phép tính: có ''N'' số ''X<sub>k</sub>'' 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.