2.2.2. Полубыстрое преобразование Фурье (ппф)
Попробуем найти алгоритм, который реализует преобразование Фурье несколько быстрее.
Идея, наводящая на алгоритм быстрого преобразования Фурье (БПФ):
Рассмотрим случай, когда N = p1·p2
Представим k и j в виде: k = k1 + p1k2 0 ≤ k ≤ N – 1
j = j2 + p2j1 0 ≤ j ≤ N – 1
Здесь k1 – остаток от деления k на p1 k1 = k mod p1
k2 – частное от деления k на p1 k1 = k div p1
0 ≤ k1 ≤ p1 – 1
0 ≤ k2 ≤ p2 – 1
аналогично
j1 – частное от деления j на p2 j1 = j div p2
j2 – частное от деления j на p2 j2 = j mod p2
0 ≤ j1 ≤ p1 - 1
0 ≤ j2 ≤ p2 - 1
Когда число j меняется от 0 до N, то j1 и j2 пробегают независимым образом все возможные значения в своих диапазонах. Поэтому, вместо однократного суммирования можно применить двукратное:
Можно игнорировать, т.к. оно добавляет к exp() = cos + i·sin целое число периодов и сама exp не меняется
A(0)(k1,k2)
A(1)(k1,j2)
A(2)(k1,k2)
Заметим, что:
Итак, мы будем вычислять преобразование Фурье не по (2.1), а по формулам (2.3а) и (2.3б):
0 ≤ k1 ≤ p1 – 1
0 ≤ j2 ≤ p2 – 1
0 ≤ k1 ≤ p1 – 1
0 ≤ j2 ≤ p2 – 1
(2.3a)
(2.3б)
Оценим трудоемкость вычисления преобразования Фурье по формулам 2.3:
Массив А(0) переходит в А(1), а оттуда в А(2):
Этот переход осуществляется в 2 этапа.
В формуле (2.3а) имеем р1 • р2 коэффициентов, каждый их которых есть сумма р1 слагаемых – итого р1 • р2 • р1 действий. В (2.3б) соответственно р1 • р2 • р2 действий. Итого
T(n) = p1·p2·p1 + p1·p2·p2 = p1·p2·(p1 + p2) = N(p1+p2).
по (2.3а) по (2.3б)
Если , то трудоемкость будет , что существенно меньше трудоемкости при обычном преобразовании Фурье. Т.е. получаем метод, позволяющий реализовать преобразование Фурье значительно быстрее. Этот метод названполубыстрым преобразованием Фурье.
Yandex.RTB R-A-252273-3
- Основные понятия. Справочный материал
- Основные понятия
- 1.2. Справочный материал. Сравнение скорости роста основных функций
- 2 Новые быстрые версии старых алгоритмов
- 2.1. Сортировки массивов
- 2.1.1 Метод прямого выбора (SelectSort)
- 2.1.2 Быстрая сортировка методом двоичных вставок (MergeSort)
- 2.2. Преобразование Фурье (бпф)
- 2.2.1. Дискретное преобразование Фурье
- 2.2.2. Полубыстрое преобразование Фурье (ппф)
- 2.2.3. Быстрое преобразование Фурье (бпф)
- 2.3. Быстрая свертка
- 2.3.1. Понятие свертки
- 2.3.2. Обычный и быстрый алгоритм свертки
- 2.4. Быстрое умножение
- 2.4.1. Быстрое умножение чисел
- 1 Суммирование
- 4 Произведения чисел вдвое меньшей
- 2.4.2. Быстрое умножение матриц
- 2.4.3. Очень быстрое умножение числе (алгоритм Шенхаге – Штрассена)
- 3. Задачи на графах
- 3.1. Справочный материал
- 3.2. Поиск минимального остова в связном неориентированном взвешенном графе
- 3.3. Нахождение кратчайшего расстояния
- 3.3.1. Алгоритм Форда – Беллмана
- 3.3.2. Алгоритм Дейкстры
- 3.4. Нахождение диаметра, радиуса и центра графа
- 3.5. Задача об изоморфизме графов
- 3.6. Задача коммивояжера. Её решение методом ветвей и границ.
- Задачи динамического программирования
- Задачи динамического программирования. Её решение методом динамического программирования.
- 4.2. Задача об оптимальном наборе самолетом скорости и высоты
- 4.3. Задача грабителя (задача о рюкзаке)
- 4.4. Задача о перемножении матриц
- 5 Классы p и np
- 5.1 Машина Тьюринга
- 5.2 Недетерменированные машины Тьюринга(ндмт)
- 5.3 Сводимость. Np-полнота.
- 5.4 Иерархия по сложности. Труднорешаемые задачи.
- Классы сложности.
- 6 Неразрешимые задачи
- 6.1 Новая модель алгоритма вычислений.
- 6.2 Нумерация программ
- 6.3 Неразрешимые проблемы
- 6.4 Теорема об ускорении
- Лабораторные работы
- Расчетно-графическое задание
- Ответы к домашним заданиям