log2N) operací
Algoritmus "decimace čase"
1. Začneme transformací
. Rychlá Fourierova transformace (FFT)
Označme N
j
e
W
π
2
−
=
pak DFT časové řady komplexních čísel je
∑
−
=
⋅
=
1
0
N
j
jn
j
n W
x
X
Přímý výpočet této transformace vyžaduje výpočet matice
[ ]
j
jn
n x
W
X ⋅
=
Například pro 8
⋅
=
7
6
5
4
3
2
1
0
49
42
35
28
21
14
7
0
42
36
30
24
18
12
6
0
35
30
25
20
15
10
5
0
28
24
20
16
12
8
4
0
21
18
15
12
9
6
3
0
14
12
10
8
6
4
2
0
7
6
5
4
3
2
1
0
0
0
0
0
0
0
0
0
7
6
5
4
3
2
1
0
x
x
x
x
x
x
x
x
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
W
X
X
X
X
X
X
X
X
Výpočet představuje komplexních sčítání násobení.3.15
m
m
N
n
t
n
f
m
j
n X
f
X
e
x
f
m
X ≈
≈
⋅
=
∆ ∑
−
=
∆
⋅
∆
⋅
−
)
(
)
(
1
0
2π
Přímý výpočet znamená N
2
operací
2.
V roce 1965 Cooley Tukley navrhli algoritmus rychlé Fourierovy transformaca (FFT),
který vyžaduje pouze (N.2
