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

n
→‎Thuật toán Cooley–Tukey: Sơ đồ BĐNF Cooley-Tukey
n (→‎Thuật toán Cooley–Tukey: replaced: {{bài chính| → {{chính| using AWB)
n (→‎Thuật toán Cooley–Tukey: Sơ đồ BĐNF Cooley-Tukey)
|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>.
[[Tập tin:BĐNF Cooley-Tukey.svg|phải|nhỏ|300px|Giải thuật biến đổi Fourier nhanh Cooley-Tukey cho mảng dài 8 phân tử]]
 
Phương pháp này (cùng với ý tưởng chung về một FFT) được phổ biến rộng rãi bởi bài báo của [[J. W. Cooley]] và [[J. W. Tukey]] năm 1965 nhưng sau đó người ta nhận ra rằng hai tác giả đó đã phát hiện lại một cách độc lập thuật toán mà [[Carl Friedrich Gauß|Carl Friedrich Gauss]] đã tìm ra khoảng năm 1805 (và sau đó được phát hiện lại nhiều lần trong những trường hợp đặc biệt).