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 →Các vấn đề tính toán: chú thích |
n chú thích, replaced: {{cite journal → {{chú thích tạp chí (2) |
||
Dòng 11:
=== Thuật toán Cooley–Tukey ===
{{main|Thuật toán FFT Cooley–Tukey}}
Thuật toán FFT phổ biến nhất là [[thuật toán Cooley-Tukey|thuật toán FFT Cooley-Tukey]]<ref>{{
|last1=Cooley
|first1=James W.
Dòng 43:
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>{{
|first1=S.
|last1=Winograd
| |||