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