Khác biệt giữa bản sửa đổi của “Biến đổi Fourier nhanh”
Nội dung được xóa Nội dung được thêm vào
n →Thuật toán Cooley–Tukey: Sơ đồ BĐNF Cooley-Tukey |
Không có tóm lược sửa đổi |
||
Dòng 1:
Một '''biến đổi Fourier nhanh (FFT)''' là một [[thuật toán]] rất hiệu quả để tính [[biến đổi Fourier rời rạc]] (DFT) và biến đổi ngược. Có nhiều thuật toán FFT khác nhau sử dụng kiến thức từ nhiều mảng khác nhau của toán học, từ [[số phức]] tới [[lý thuyết nhóm]] và [[lý thuyết số]]. Bài này chỉ giới thiệu tổng quan các kĩ thuật và một số tính chất tổng quát. Các thuật toán cụ thể được mô tả chi tiết hơn trong các bài khác được liên kết ở dưới.
Phép biến đổi DFT phân tích một dãy các số thành các thành phần ở các tần số khác nhau. Nó được sử dụng trong nhiều lĩnh vực khác nhau (xem các tính chất và ứng dụng ở [[biến đổi Fourier rời rạc]]) nhưng tính toán trực tiếp từ định nghĩa thường quá chậm trong thực tế. FFT là một cách để đạt được cùng kết quả đó nhưng nhanh hơn nhiều: tính DFT của ''N'' điểm trực tiếp theo định nghĩa đòi hỏi [[kí hiệu O lớn|O]](''N<sup>2</sup>'') phép tính, trong khi FFT tính ra cùng kết quả đó trong O(''N'' log ''N'') phép tính.
| |||