Поняття про швидкі алгоритми

При побудові швидких алгоритмів використовують кілька основних прийомів. Серед них найголовнішими є :

1. Розбиття задачі на підзадачі.

2. Рекурсія - коли деякий метод чи прийом можна рекурсивно застосовувати;

3. Виділення алгебраїчних виразів, що повторюються.

На основі цих прийомів і побудований алгоритм швидкого перетворення Фур’є Кулі – Т’юкі. При чому, в залежності від того, як саме виконується той чи інший етап, утворюється певний вид ШПФ.

 

ШПФ за основою 2 та прорідженням за часом (ШПФ2t)

1. Розбиття задачі на підзадачі. Розбиття (поділ) вхідної послідовності в цьому виді ШПФ здійснюється за принципом парності/непарності відліків. Тобто початкова сума розбивається на дві вдвічі меншої розмірності, перша з яких містить відліки з парними індексами, друга – з непарними.

.

Оскільки : ;

,

2. Рекурсія. Рекурсивно продовжуючи за формулою розкладу розбиття перетворення меншої розмірності, тобто та аж до отримання двоточкових перетворень, синтезуємо потрібний алгоритм ШПФ.

3. Виділення однакових виразів. Цей етап виконується для того, щоб однакові вирази обчислювати лише один раз. Тут беруться до уваги властивості періодичності симетричності повертаючих множників.

Періодичність :

; .

Симетричність :

; .

Крім того, самі послідовності та є періодичні з періодом N/2 (оскільки вони є ДПФ для N/2 точок), тобто : , . Тому в загальній формулі розкладу для другої половини коефіцієнтів, тобто для k+N/2, будемо мати:

.

Таким чином, маємо основну процедуру швидкого алгоритму:

.

Вона визначає правило обчислення N- точкового ДПФ за результатами двох ДПФ розмірності N/2 для парних і непарних вхідних відліків.

Основною операцією алгоритму ШПФ, яку ще називають базовою операцією (БО) є одночасне (паралельне) обчислення двох відліків ДПФ – k- того та k+N/2- того, за наведеною вище формулою. Граф БО отримав назву «метелик» :

Базова операція алгоритму ШПФ з часовим прорідженням

 

Граф-схема алгоритму 8- точкового ШПФ2t

Оцінка обчислювальної складності алгоритму ШПФ. Алгоритм N - точкове ШПФ2t буде складатися з log2N етапів, на кожному з яких буде виконуватися N/2 БО. Тобто всього буде виконано log2N*N/2 БО. Враховуючи, що для виконання одного «метелика» треба виконати 1 операцію комплексного множення то 2 операції комплексного додавання, оцінимо складність такого алгоритму.

;

Характеристики обчислювальної складності N – точкового алгоритму ШПФ2t:

- кількість операцій комплексного множення ;

- кількість операцій додавання .

Порівнявши характеристики складності можна говорити, що побудований алгоритм є швидкий, оскільки він зменшує характеристики складності на порядок.

; .