Здесь a называется вещественной (Real) частью, а b мнимой (Imaginary). В этих числах, как нетрудно заметить, можно извлекать корень из отрицательных (да и вообще любых) чисел это очень удобно при работе с многочленам как следует из основной теоремы алгебры, у каждого многочлена степени n имеется ровно n комплексных корней (с учётом кратности).
Если Вы знакомы с комплексными числами, то можете пропустить этот пункт, в противном случае, вот краткое определение:
Для начала давайте определимся, что такое многочлен:
Определения и способы применения
БПФ это алгоритм, вычисляющий значения многочлена степени n=2k в некоторых n точках за время O(n logn) («наивный» метод выполняет ту же задачу за время O(n2)). За то же время можно выполнить и обратное преобразование. Так как складывать, вычитать и умножать массивы чисел гораздо легче, чем многочлены (особенно умножать), БПФ часто применяется для ускорения вычислений с многочленами и длинными числами.
Этот пост посвящён быстрому преобразованию Фурье. Будут рассмотрены прямое и обратное преобразования (в комплексных числах). В следующей части я планирую рассмотреть их применения в некоторых задачах олимпиадного программирования (в частности, одна задача про «похожесть» строк), а также рассказать про реализацию преобразования в целых числах.
Быстрое умножение многочленов при помощи преобразования Фурье это просто
Быстрое умножение многочленов при помощи преобразования Фурье это просто / Хабрахабр
Комментариев нет:
Отправить комментарий