Страница 1 из 1

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

Добавлено: 31 мар 2017, 15:58
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 раз ниже чем если бы мы считали линейную свертку в лоб.

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

Добавлено: 01 апр 2017, 12:03
Бахурин Сергей
На самом деле написано верно, но для читателя не совсем очевидно. Поскольку это пример расчета линейной свертки, а не циклической, то доплнять нулями надо до длины M+N-1 = 6999, чтобы свести циклическую свертку к линейной. И потом уже дополнять до целой степени 2, т.е. до 8192.

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