БПФ Кули-Тьюки

В ДПФ (12.17):

, (12.17)

где

, (12.19)

определим количество арифметических операций с комплексными числами:

при

всего, при

Порядок вычислительной сложности относительно длины последовательности N:

.

БПФ — это

БПФ Кули-Тьюки (БПФ по основанию 2) — длина исходной последовательности:

. (13.1)

Основная идея — поэтапное вычисление ДПФ через ДПФ вдвое меньшей последовательности. Всего этапов.