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

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

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

Сообщение Nevendaar »

Здравствуйте! Почитал статью 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 раз ниже чем если бы мы считали линейную свертку в лоб.

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

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

Сообщение Бахурин Сергей »

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

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

Ответить