📄 fft.html

📁 Data Structure Ebook
💻 HTML
字号:
<HTML><HEAD>
<TITLE>Data Structures and Algorithms: Fast Fourier Transforms</TITLE>

<META name="description" content="Data Structures and Algorithms Course Notes,
PLDS210 University of Western Australia">
<META name="keywords" content="data structures,algorithms,abstract data types ">
</HEAD>
<BODY BGCOLOR="#ffffff">
<TABLE BGCOLOR="#00c0f0" WIDTH="100%" CELLSPACING=0 CELLPADDING=0>
<TR BGCOLOR="#00f0f0"><TD ALIGN=right>
<FONT FACE=helvetica SIZE=+1><I>Data Structures and Algorithms</I></FONT>
</TD></TR>

<TR><TD><FONT FACE=helvetica SIZE=+2><B>12 Fast Fourier Transforms</B></FONT>
</TD></TR>
</TABLE>
<P>

Fourier transforms have wide application in scientific and
engineering problems,
for example, they are extensively used in signal processing to
transform a signal from the time domain to the frequency 
domain.
<P>
Here, we will use them to generate an efficient solution to
an apparently unrelated problem - that of multiplying two
polynomials.
Apart from demonstrating how the Fast Fourier Transform
(FFT)
algorithm calculates a Discrete Fourier Transform and
deriving its time complexity,
this approach is designed to reinforce the
following points:
<UL>
<LI> 'Better' solutions are known to many problems
for which, intuitively, it would not appear possible to
find a better solution.
<LI> As a consequence,
unless you have read extensively in any problem area
already, 
you should consult the literature before attempting to
solve any numerical or data processing problem
presented to you.
</UL>
<P>
Because of the limitations of HTML in handling
mathematical equations, the notes for this section
were prepared with LaTeX and are available as a
<A HREF="fft.ps" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/latex/fft.ps">PostScript file</A>.
<P>


<TABLE CELLPADDING=5 WIDTH="100%" BGCOLOR="#00f0f0" CELLSPACING=4>
<TR><TD WIDTH=50%>
Continue on to <A HREF="hard.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/hard.html">Hard Problems</A></TD>
<TD>Back to the <A HREF="ds_ToC.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/ds_ToC.html">Table of Contents</A>
</TD></TR></TABLE>
<SMALL>
&copy; <A HREF=mailto:morris@ee.uwa.edu.au>John Morris</A>, 1998
</SMALL>
</BODY>
</HTML>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -