Здравствуйте! Почитал статью 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 раз ниже чем если бы мы считали линейную свертку в лоб.
Возможная неточность в вычислении сложности
- Бахурин Сергей
- Администратор
- Сообщения: 1116
- Зарегистрирован: 05 окт 2010, 19:55
- Контактная информация:
Re: Возможная неточность в вычислении сложности
На самом деле написано верно, но для читателя не совсем очевидно. Поскольку это пример расчета линейной свертки, а не циклической, то доплнять нулями надо до длины M+N-1 = 6999, чтобы свести циклическую свертку к линейной. И потом уже дополнять до целой степени 2, т.е. до 8192.
Спасибо, что обратили внимание. При переработке обязательно учту замечание, чтобы отметить этот момент.
Спасибо, что обратили внимание. При переработке обязательно учту замечание, чтобы отметить этот момент.