Я просматриваю указанную выше тему из CLRS (CORMEN) (страница 834), и я застрял на этом месте.
Может ли кто-нибудь объяснить, как следующее выражение,
A(x)=A^{[0]}(x^2) +xA^{[1]}(x^2)
следует из,
n-1 `
Σ a_j x^j
j=0
Где,
A^{[0]} = a_0 + a_2x + a_4a^x ... a_{n-2}x^{\frac{n}{2-1}}
A^{[1]} = a_1 + a_3x + a_5a^x ... a_{n-1}x^{\frac{n}{2-1}}
Полином A(x) определяется как
A(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + ...
Чтобы запустить стратегию «разделяй и властвуй» полиномиального умножения с помощью БПФ, CLRS вводит два новых полинома: один из коэффициентов при четных степенях x, называемый A[0], и один из коэффициентов при нечетных степенях x, называемый A[1].
A[0](x) = a_0 + a_2 x + a_4 x^2 + ...
A[1](x) = a_1 + a_3 x + a_5 x^2 + ...
Теперь, если мы подставим x^2 в A[0] и A[1], мы получим
A[0](x^2) = a_0 + a_2 x^2 + a_4 x^4 + ...
A[1](x^2) = a_1 + a_3 x^2 + a_5 x^4 + ...
и если мы умножим A[1](x^2) на x, мы получим
x A[1](x^2) = a_1 x + a_3 x^3 + a_5 x^5 + ...
Теперь, если мы добавим A[0](x^2) и x A[1](x^2), мы получим
A[0](x^2) + x A[1](x^2) = (a_0 + a_2 x^2 + a_4 x^4 + ...) + (a_1 x + a_3 x^3 + a_5 x^5 + ...)
= a_0 + a_1 x + a_2 x^2 + a_3 x^3 + ...
= A(x)
Q.E.D.
Если вы разделите многочлен на «нечетные степени» и «четные степени», вы обнаружите раздражающий факт, что полином A[1] (тот, что с нечетными показателями) имеет нечетные степени! Даже с показателями легче работать для БПФ. Таким образом, можно просто вынести один «x» из всех значений в A[1] и переместить его за пределы выражения.
БПФ любит работать только с полиномами с четной экспонентой. Таким образом, когда вы выполняете принцип «разделяй и властвуй», вы хотите превратить выражение A[1] в полином с «четной экспонентой», выполнить рекурсию по нему и затем умножить обратно. что х. Вы увидите, что это происходит во внутреннем цикле фактического алгоритма.
Редактировать: я понимаю, что ваше замешательство может быть связано с тем фактом, что они "передаются" (x^2) как значение в многочлене. «x» в A[1] и A[0] отличается от x в выражении (x^2). Вы увидите, как это должно быть, поскольку в то время как исходный многочлен A возрастает до степени N, A[1] и A[0] оба возрастают только до степени (N/2).
Я не собираюсь отвечать на ваш вопрос, потому что я чувствую, что предыдущие люди ответили на него. Что я сделаю, так это попытаюсь объяснить цель БПФ.
Во-первых, БПФ — это способ вычисления свертки между двумя векторами. То есть предположим, что x = и y= являются векторами 1xn, тогда свертка x и y равна
\sum_{i=0} ^n {xi y{n-i}}.
Вам придется принять тот факт, что вычисление этого значения ЧРЕЗВЫЧАЙНО полезно в широком диапазоне приложений.
Теперь рассмотрим следующее.
Предположим, мы построили два многочлена
A(z) = x0 + x1*z + x2 *z^2 + .. + xn^z^n B(z) = y0 + y1*z + y2 *z^2 + .. + yn^z^n
тогда умножение равно
AB(z) = A(z)B(z) = \sum_{i=0} ^ n (\sum_{k=0} ^ i xk*y{ik}) z^i
где внутренняя сумма явно является сверткой разного размера для разных значений k.
Теперь мы можем явно вычислить коэффициенты (свертки) AB за время n^2 методом грубой силы.
Однако мы также можем быть намного умнее. Учтите, что любой многочлен степени n можно однозначно описать n+1 точками. То есть по n+1 точкам мы можем построить единственный многочлен степени n, который проходит через все n+1 точек. Далее рассмотрим 2 многочлена в виде n+1 точек. Вы можете вычислить их произведение, просто умножив n+1 значений y и сохранив значения x, чтобы получить их произведение в точечной форме. Теперь, имея полином в n+1 точечной форме, вы можете найти уникальный полином, который описывает его за время O(n) (на самом деле я не уверен в этом, это может быть время O(nlogn), но точно не больше.)
Это именно то, что делает БПФ. Однако точки, которые он выбирает, чтобы получить n+1 точек для описания многочленов A и B, выбираются ОЧЕНЬ тщательно. Некоторые точки действительно сложны, потому что так получилось, что вы можете сэкономить время при оценке многочлена, рассматривая такие точки. То есть, если бы вы выбрали только реальные точки вместо тщательно выбранных точек, которые использует БПФ, вам потребовалось бы время O (n ^ 2) для оценки n + 1 точки. Если вы выберете БПФ, вам потребуется только O (nlogn) времени. И это все, что нужно для БПФ. О, и есть уникальный побочный эффект в том, как БПФ выбирает точки. Учитывая полином n-й степени, вы должны выбрать 2 ^ m точек, где m выбрано так, чтобы 2 ^ m было наименьшей степенью числа 2, большей или равной n.
