7.6. Эффективность алгоритма БПФ
При непосредственном вычислении ДПФ, рассмотренном ранее и иллюстрируемом фиг. 7.9, для вычисления каждого из 
значений 
требуется 
комплексных умножений. Поскольку умножение — самая медленная из всех операций, выполняемых на ЦВМ, то время, необходимое для вычисления ДПФ таким способом, будет почти точно пропорционально 
С другой стороны, исследуя направленный граф на фиг. 7.12 г находим, что БПФ требует 
комплексных умножений. Действительно, конечный или любой промежуточный массив 
получается из предыдущего с помощью 
взвешиваний, каждое из которых включает одно комплексное умножение. Всего таких циклов взвешивания 
причем
Для больших значений N БПФ значительно сокращает время вычислений. Например, если 
оказывается приблизительно в 100 раз быстрее обычного ДПФ.
