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

không có tóm lược sửa đổi
|pages=297–301
}}</ref>. Đây là một [[thuật toán chia để trị]] dùng [[đệ quy]] để chia bài toán tính DFT có kích thước [[hợp số]] ''N=N<sub>1</sub>N<sub>2</sub>'', thành nhiều bài toán tính DFT nhỏ hơn có kích thước ''N<sub>1</sub>'' và ''N<sub>2</sub>'', cùng với O(''N'') phép nhân với [[căn của đơn vị]], thường được gọi là [[thừa số xoay]] (theo Gentleman và Sande, 1966)<ref>{{cite conference|author=W. M. Gentleman, G. Sande|year=1966|title=Fast Fourier Transforms: for fun and profit|booktitle=Proceedings of the November 7-10, 1966, fall joint computer conference (AFIPS '66 (Fall))|publisher=ACM, New York, NY, USA|pages=563-578|doi=10.1145/1464291.1464352|url=http://doi.acm.org/10.1145/1464291.1464352}}</ref>.
 
==Các vấn đề tính toán==
{{Vấn đề mở|khoa học máy tính|Chặn dưới của độ phức tạp tính toán của biến đổi Fourier nhanh là gì? Liệu nó có thể nhanh hơn &Theta;(N log N) hay không?}}
 
Một bài toán mở quan trọng về mặt lý thuyết là chứng minh chặn dưới cho độ phức tạp tính toán và số phép tính của biến đổi Fourier nhanh. Hiện vẫn chưa có chứng minh nào cho việc DFT có thực sự đòi hỏi Ω(''N'' log ''N'') phép tính, ngay cả trong trường hợp kích thước ''N'' là lũy thừa của hai, mặc dù không có thuật toán nào có độ phức tạp thấp hơn. Chú ý rằng tuy số phép tính thường là quan tâm chính về mặt lý thuyết, trên thực tế, tốc độ thực thi phụ thuộc nhiều yếu tố khác như các tối ưu hóa cho [[bộ nhớ đệm]] và [[ống lệnh CPU]].
 
Theo công trình của Winograd năm 1978<ref>{{cite journal
|first1=S.
|last1=Winograd
|year=1978
|doi=10.1090/S0025-5718-1978-0468306-4
|title=On computing the discrete Fourier transform
|journal=Math. Computation
|volume=32
|issue=141
|pages=175&ndash;199
}} {{JSTOR|2006266}}</ref>, chặn dưới chặt cho số phép nhân của FFT đã được biết là &Theta;(''N'').
==Xem thêm==
* [[Thuật toán FFT Bruun]]
* [[Thuật toán FFT Rader]]
* [[Thuật toán FFT Bluestein]]
* [[Biểu đồ cánh bướm]] - một biểu đồ minh họa cho FFT.
* [[Thuật toán Odlyzko–Schönhage]] áp dụng FFT cho [[chuỗi Dirichlet]]
* [[FFTW]] "Fastest Fourier Transform in the West" - Thư viện viết bằng 'C' để tính biến đổi Fourier rời rạc (DFT) trong một hay nhiều chiều
* [[FFTPACK]] - một thư viện FFT khác cho C và Java
==Ghi chú==
{{reflist}}
494

lần sửa đổi