[Из песочницы] Преобразование Фурье. The Fast and the Furious

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

Читать дальше →
[Из песочницы] Преобразование Фурье. The Fast and the Furious
Source: habrahabr