Возможная неточность в вычислении сложности

Ответить
Nevendaar
Сообщения: 1
Зарегистрирован: 31 мар 2017, 15:32

Возможная неточность в вычислении сложности

Сообщение Nevendaar » 31 мар 2017, 15:58

Здравствуйте! Почитал статью http://www.dsplib.ru/content/conv/conv.html. Заметил возможную ошибку в вычислении оценки сложности алгоритма через БПФ. Мы дополняем 0 M = 4000 и N = 3000 до ближайшей степени двойки. В примере дополняется до 13 степени двойки, т.е. до 8192, тогда как ближайшая - 12 степень, т.е. 4096. И в итоге сложность уменьшается ещё больше.

Рассмотрим пример. Пусть N = 4000, а M = 3000. Прямое вычисление линейной свертки потребует N*M = 12 000 000 операций умножения и сложения.
Дополним каждую из последовательностей до 4096 отсчетов нулями и применим алгоритм БПФ с прореживание по времени, тогда на вычисление одного БПФ потребуется N * log2(N) = 4096 * 12 = 50000(примерно) операций комплексного умножения или 200 000 операций действительного умножения. Таких блоков БПФ будет всего 3 штуки, плюс надо учесть 4096 комплексных умножений спектров, итого 200 000 * 3 + 4096 * 4 = 617 000(примерно) , что почти в 20 раз ниже чем если бы мы считали линейную свертку в лоб.

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 623
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

Re: Возможная неточность в вычислении сложности

Сообщение Бахурин Сергей » 01 апр 2017, 12:03

На самом деле написано верно, но для читателя не совсем очевидно. Поскольку это пример расчета линейной свертки, а не циклической, то доплнять нулями надо до длины M+N-1 = 6999, чтобы свести циклическую свертку к линейной. И потом уже дополнять до целой степени 2, т.е. до 8192.

Спасибо, что обратили внимание. При переработке обязательно учту замечание, чтобы отметить этот момент.

Ответить

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 1 гость