Быстрое преобразование Фурье (БПФ): самый гениальный алгоритм в истории?

В этом видео мы рассмотрим один из самых красивых алгоритмов, когда-либо созданных: быстрое преобразование Фурье (БПФ). Этот алгоритм довольно сложен для понимания, поэтому мы рассмотрим его в контексте, знакомом всем: умножение многочленов. Вы увидите, как основные идеи БПФ можно «открыть», задавая правильные вопросы. Ключевые выводы, представленные в этом видео, заключаются в том, что умножение многочленов можно значительно улучшить, умножая многочлены в специальном представлении значений. Задача, которая здесь стоит, — это преобразование многочлена из стандартного представления коэффициентов в представление значений. Мы видим, что БПФ — это невероятно эффективный рекурсивный алгоритм, выполняющий эту задачу, а также обнаруживаем, что слегка модифицированное БПФ (обратное БПФ) может решить и обратную задачу интерполяции. Если это видео вас не впечатлит, я не знаю, что ещё сможет. Исправление ошибки: на отметке 26:40 вместо замены w на (1/n * e^{-2 * pi i/ n}) правильный способ сделать это — взять конечный результат обратного быстрого преобразования Фурье в конце рекурсии и разделить на n. Таким образом, полное изменение равно w = e^{-2 pi i / n} А затем где-то за пределами области действия функции обратного быстрого преобразования Фурье ifft_result = 1/n * IFFT Представленный в этом видео подход к рассмотрению БПФ основан на нескольких известных источниках, в основном на книгах «Введение в алгоритмы» (Кормен и др.) и «Алгоритмы» (Пападимитриу и др.).