Задача состоит в том, чтобы вычислить многочлен . Предположим, что все коэффициенты вписываются в машинное слово, т. Е. Ими можно манипулировать в единицу времени.
Вы можете сделать раз, применяя БПФ в виде дерева. Ты можешь сделать O ( n log n ) ?
Задача состоит в том, чтобы вычислить многочлен . Предположим, что все коэффициенты вписываются в машинное слово, т. Е. Ими можно манипулировать в единицу времени.
Вы можете сделать раз, применяя БПФ в виде дерева. Ты можешь сделать O ( n log n ) ?
Ответы:
Предупреждение: это еще не полный ответ. Если аргументы правдоподобности делают вас неудобными, прекратите читать.
Я рассмотрю вариант, в котором мы хотим умножить (x - a_1) ... (x - a_n) на комплексные числа.
Задача двойственна оценке полинома в n точках. Мы знаем, что это можно сделать умно за O (n log n), когда точки оказываются n-ю корнями единства. Это существенно использует симметрии правильных многоугольников, которые лежат в основе быстрого преобразования Фурье. Это преобразование существует в двух формах, условно называемых «прореживание во времени» и «прореживание по частоте». В основании два они полагаются на двойную пару симметрий четных правильных многоугольников: симметрия взаимосвязи (правильный шестиугольник состоит из двух взаимно соединяющихся равносторонних треугольников) и симметрия разворачивания веера (разрезаем правильный шестиугольник пополам и разворачиваем части как вееры). в равносторонние треугольники).
С этой точки зрения кажется невероятным, что алгоритм O (n log n) будет существовать для произвольного набора из n точек без особых симметрий. Это означало бы, что в правильных многоугольниках нет ничего исключительного в алгоритме по сравнению со случайными наборами точек на комплексной плоскости.
источник