Повторное разбиение последовательностей

Если необходимо получить преобразование Фурье заданной последовательности, то можно выполнить разбиение последовательности на две части и осуществить преобразование каждой из этих частей в отдельности. Так как затрачиваемое время возрастает быстрее скорости изменения N, при реализации преобразования будет иметь место экономия времени счета; однако потребуется некоторое дополнительное время, так как два коротких преобразования объединяются каким-либо образом с целью получения совокупного более длинного преобразования. Данная идея представляется заманчивой, так как подобная процедура может быть применена вновь, а именно сами эти короткие последовательности могут быть поделены пополам с целью дальнейшей экономии времени. В принципе любая факторизация приводит к упрощению вычислительной процедуры. После выполнения разбиения исходной последовательности получим двухэлементные сегменты. Теперь уже преобразование двухэлементной последовательности является тривиальным и включает в себя два действия сложения и ни одного действия умножения. Количество

операций, требуемых для объединения последовательностей, получаемых на каждом этапе разбиения, имеет порядок величины N, так как каждому из N элементов может быть присвоен некоторый коэффициент, а всего имеется (Р — 1) этапов разбиения. Следовательно, при достаточно больших N количество операций определяется как N (Р — 1) или приближенно как

Так же как и при обосновании закона вида рассуждения в подтверждение закономерности вида носят приближенный характер. Теперь мы подробно проанализируем механизм формирования преобразования Хартли. Далее мы выполним эмпирическую проверку временных затрат на реализацию преобразования в рамках анализа, заменяющего процедуру подсчета количества операций.