"Дерево" для оценки полинома быстрого преобразования Фурье?

Question

Я пытаюсь оценить полином A(x) с помощью алгоритма "разделяй и властвуй", используя БПФ. Я в основном разбиваю многочлен на его нечетные корни и четные корни, а затем рекурсирую по двум меньшим многочленам (что позволяет мне оценивать двойные числовые значения за рекурсию).

Чтобы визуализировать это, я пытаюсь создать дерево, чтобы показать путь полинома через алгоритм. Я не совсем уверен, с чего начать - кто-то может просто начать меня? Я не ожидаю, что полное дерево, просто краткий пример, поможет мне выбрать правильный путь.

Answer 1

Вот простой пример из Главы 2 Алгоритмов:

A(x) = 3 + 4x + 6x^2 + 2x^3 + x^4 + 10x^5
     = (3 + 6x^2 + x^4) + x(4 + 2x^2 + 10x^4)
     = E(x^2) + x*O(x^2)

где

E(x) = 3 + 6x + x^2
O(x) = 4 + 2x + 10x^2

Заметьте, как размер полинома сократился в 2 раза? Кроме того, мы можем переработать оценку в x поскольку -x приведет к аналогичному значению.

A(x) = E(x^2) + x*O(x^2)
A(-x) = E(x^2) - x*O(x^2)

Я надеюсь, вы можете увидеть, как этот рекурсивный процесс становится деревом.