Быстрое преобразование Фурье: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Lukoshkin (обсуждение | вклад) →Основной алгоритм: Добавлен новый заголовок, лишнее было выброшено, статья стала более структурированной и наглядной, исправлены ошибки |
Lukoshkin (обсуждение | вклад) |
||
Строка 24:
# Вычисляем каждое <math>b_i</math>, где <math>i=\overline{0,p-1}</math>. Здесь по-прежнему требуется совершить <math>O(N)</math> действий. То есть на этом этапе производится <math>p\cdot O(N)=O(Np)</math> операций.
# Далее считаем <math>b_{i+mp}</math>, где <math>i=\overline{0,p-1}, m=\overline{1,q-1}</math>. Заменой <math>i\longmapsto i+mp</math> в последней формуле, убеждаемся в том, что выражения стоящие в скобках остались неизменными. А так они уже были посчитаны на предыдущем шаге, то на вычисления каждого из них потребуется только <math>O(q)</math> действий. Всего <math>p(q-1)=N-p</math> чисел. Следовательно операций на этом шаге <math>(N-p)\cdot O(q)=O((N-1)q)\cong O(Nq)</math>. Последнее с хорошей точностью верно при любых N. Но стоит также упомянуть, что алгоритм БПФ логично применять для <math>N\gg1</math>, потому как при малом числе отсчётов он даёт небольший выигрыш в скорости по отношению к ДПФ.
Таким образом, для того чтобы полностью перейти к набору чисел <math>b_0, \dots, b_{N-1}</math>, необходимо <math>O(Np)+O(Nq)</math> действий. Следовательно, нет разницы на какие два числа разбивать N - ответ от этого сильно не будет меняться. Уменьшено же число операций может быть только дальнейшим разбиением N.
Скорость алгоритма (N=pq):
# <math>p\gg q</math>. <math>O(Np)</math>
# <math>p\sim q</math> <math>O(Nq)</math>
| |||