Discrete Fourier Transform: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 18: | Line 18: | ||
| [[Naive algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Naive algorithm]] || 1965 || $O(n^{2})$ || $O({1})$ || Exact || Deterministic || | | [[Naive algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Naive algorithm]] || 1965 || $O(n^{2})$ || $O({1})$ || Exact || Deterministic || | ||
|- | |- | ||
| [[Cooley–Tukey algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Cooley–Tukey algorithm]] || 1965 || $O( | | [[Cooley–Tukey algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Cooley–Tukey algorithm]] || 1965 || $O(n \log n)$ || $O(n)$? || Exact || Deterministic || [https://www.ams.org/journals/mcom/1965-19-090/S0025-5718-1965-0178586-1/S0025-5718-1965-0178586-1.pdf Time] | ||
|- | |- | ||
| [[Rader–Brenner algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Rader–Brenner algorithm]] || 1976 || $O( | | [[Rader–Brenner algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Rader–Brenner algorithm]] || 1976 || $O(n \log n)$ || $O(n)$? || Exact || Deterministic || [https://ieeexplore.ieee.org/document/1162805 Time] | ||
|- | |- | ||
| [[Bruun's FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Bruun's FFT algorithm]] || 1978 || $O( | | [[Bruun's FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Bruun's FFT algorithm]] || 1978 || $O(n \log n)$ || $O(n)$? || Exact || Deterministic || [https://ieeexplore.ieee.org/document/1163036/ Time] | ||
|- | |- | ||
| [[Yavne Split Radix FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Yavne Split Radix FFT algorithm]] || 1968 || $O( | | [[Yavne Split Radix FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Yavne Split Radix FFT algorithm]] || 1968 || $O(n \log n)$ || $O(n)$? || Exact || Deterministic || [https://dl.acm.org/citation.cfm?id=1476610 Time] | ||
|- | |- | ||
| [[Gentleman; Morven and Gordon Sande radix-4 algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Gentleman; Morven and Gordon Sande radix-4 algorithm]] || 1966 || $O( | | [[Gentleman; Morven and Gordon Sande radix-4 algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Gentleman; Morven and Gordon Sande radix-4 algorithm]] || 1966 || $O(n \log n)$ || $O(n)$? || Exact || Deterministic || [http://cis.rit.edu/class/simg716/FFT_Fun_Profit.pdf Time] | ||
|- | |- | ||
| [[Bergland; Glenn radix-8 algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Bergland; Glenn radix-8 algorithm]] || 1969 || $O( | | [[Bergland; Glenn radix-8 algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Bergland; Glenn radix-8 algorithm]] || 1969 || $O(n \log n)$ || $O(n)$ || Exact || Deterministic || [https://ieeexplore.ieee.org/document/1162043 Time & Space] | ||
|- | |- | ||
| [[Extended Split Radix FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Extended Split Radix FFT algorithm]] || 2001 || $O( | | [[Extended Split Radix FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform)|Extended Split Radix FFT algorithm]] || 2001 || $O(n \log n)$ || $O(n)$? || Exact || Deterministic || [https://ieeexplore.ieee.org/document/917698 Time] | ||
|- | |- | ||
| [[ Von zur Gathen-Gerhard additive FFT (Discrete Fourier Transform Discrete Fourier Transform)| Von zur Gathen-Gerhard additive FFT]] || 1996 || $O(n ( | | [[ Von zur Gathen-Gerhard additive FFT (Discrete Fourier Transform Discrete Fourier Transform)| Von zur Gathen-Gerhard additive FFT]] || 1996 || $O(n (\log n)$^{2}) || $O(n)$ || Exact || Deterministic || [https://dl.acm.org/doi/10.1145/236869.236882 Time & Space] | ||
|- | |- | ||
| [[Wang-Zhu-Cantor additive FFT (Discrete Fourier Transform Discrete Fourier Transform)|Wang-Zhu-Cantor additive FFT]] || 1988 || $O(n( | | [[Wang-Zhu-Cantor additive FFT (Discrete Fourier Transform Discrete Fourier Transform)|Wang-Zhu-Cantor additive FFT]] || 1988 || $O(n(\log n)$^{1.{58}5}) || $O(n)$? || Exact || Deterministic || [https://ieeexplore.ieee.org/document/1926/ Time] | ||
|- | |- | ||
| [[Gao’s additive FFT (Discrete Fourier Transform Discrete Fourier Transform)|Gao’s additive FFT]] || 2010 || $O(n logn loglogn)$ || $O(n)$ || Exact || Deterministic || [https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5625613 Time & Space] | | [[Gao’s additive FFT (Discrete Fourier Transform Discrete Fourier Transform)|Gao’s additive FFT]] || 2010 || $O(n logn loglogn)$ || $O(n)$ || Exact || Deterministic || [https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5625613 Time & Space] | ||
| Line 40: | Line 40: | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:Discrete Fourier Transform - Time.png|1000px]] | [[File:Discrete Fourier Transform - Time.png|1000px]] | ||
Latest revision as of 09:08, 28 April 2023
Description
In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency.
Parameters
$n$: length of the input data set
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Naive algorithm | 1965 | $O(n^{2})$ | $O({1})$ | Exact | Deterministic | |
| Cooley–Tukey algorithm | 1965 | $O(n \log n)$ | $O(n)$? | Exact | Deterministic | Time |
| Rader–Brenner algorithm | 1976 | $O(n \log n)$ | $O(n)$? | Exact | Deterministic | Time |
| Bruun's FFT algorithm | 1978 | $O(n \log n)$ | $O(n)$? | Exact | Deterministic | Time |
| Yavne Split Radix FFT algorithm | 1968 | $O(n \log n)$ | $O(n)$? | Exact | Deterministic | Time |
| Gentleman; Morven and Gordon Sande radix-4 algorithm | 1966 | $O(n \log n)$ | $O(n)$? | Exact | Deterministic | Time |
| Bergland; Glenn radix-8 algorithm | 1969 | $O(n \log n)$ | $O(n)$ | Exact | Deterministic | Time & Space |
| Extended Split Radix FFT algorithm | 2001 | $O(n \log n)$ | $O(n)$? | Exact | Deterministic | Time |
| Von zur Gathen-Gerhard additive FFT | 1996 | $O(n (\log n)$^{2}) | $O(n)$ | Exact | Deterministic | Time & Space |
| Wang-Zhu-Cantor additive FFT | 1988 | $O(n(\log n)$^{1.{58}5}) | $O(n)$? | Exact | Deterministic | Time |
| Gao’s additive FFT | 2010 | $O(n logn loglogn)$ | $O(n)$ | Exact | Deterministic | Time & Space |
Time Complexity Graph
