Зачастую при разработке алгоритмов мы упираемся в предел вычислительной сложности, который, казалось бы, преодолеть невозможно. Преобразование Фурье имеет сложность $$, а быстрый вариант, предложенный около 1805 года Гаусом¹ (и переизобретенный в 1965 году Джеймсом Кули и Джоном Тьюки) $$. В данной статье хочу вам показать, что можно получить результаты преобразования за линейное время $$ или даже достичь константной сложности $$ при определенных условиях, которые встречаются в реальных задачах.

Читать дальше ->

https://habr.com/post/434734/?utm_source=habrahabr&utm_medium=rss&utm_campaign=434734