В ДПФ (12.17):
, (12.17)
где
, (12.19)
определим количество арифметических операций с комплексными числами:
при
всего, при
Порядок вычислительной сложности относительно длины последовательности N:
.
БПФ — это
БПФ Кули-Тьюки (БПФ по основанию 2) — длина исходной последовательности:
. (13.1)
Основная идея — поэтапное вычисление ДПФ через ДПФ вдвое меньшей последовательности. Всего этапов.