Эффективность алгоритма БПФ

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

ü количество этапов —

ü количество бабочек на одном этапе —

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

ИТОГО — операций.

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

.

Определить выигрыш в количестве операции по сравнению с ДПФ для 1024.