我正在研究 CLRS(CORMEN) ( page 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 + ...
为了启动 FFT 多项式乘法的分而治之策略，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.
关于algorithm - 使用快速傅立叶变换的多项式乘法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1257010/