5,323
edits
Fourier transform: Difference between revisions
→Discrete Fourier Transform
| Line 16: | Line 16: | ||
===Discrete Fourier Transform=== | ===Discrete Fourier Transform=== | ||
{{ | {{Main | Wikipedia: Discrete Fourier transform}} | ||
A naive DFT would compute the matrix of <math>e^{-i2 \pi \xi x}</math> and multiply it with the signal. This would take <math>\mathcal{O}(n^2)</math> time.<br> | A naive DFT would compute the matrix of <math>e^{-i2 \pi \xi x}</math> and multiply it with the signal. This would take <math>\mathcal{O}(n^2)</math> time.<br> | ||
However, most languages have an FFT library which can compute the DFT in <math>\mathcal{O}(n \log n)</math> time. | However, most languages have an FFT library which can compute the DFT in <math>\mathcal{O}(n \log n)</math> time. | ||