Быстрое преобразование Фурье

•Вышеприведенные соотношения подсказывают метод сокращения числа комплексных умножений вдвое. Так

как

wN 2 1

N

, эти соотношения можно записать в

виде:

x

( p)

1

( p) w

r

m 1

2

m

N

m

x

(q)

1

r

x

2

x ( p) w

(q) .

m 1

m

N

m

• Так как на каждую ступень разбиения имеется

N 2

таких операций, а общее число ступеней равно

log2 N ,

то общее число пар операций «умножение-сложение»

сокращается до

N

log2 N .

2