我目前正在学习FFT，在解决以下问题时遇到困难：
编写一个"分而治之"算法，将两个复杂度多项式（最大N次）相乘：
n^log3（基2 log-ofc）的数据
该算法应将两个给定的多项式系数分为两组：
Group1）具有偶数索引的系数。Group2）具有奇数索引的系数。
嗯，我甚至不知道如何开始考虑解决方案。。指南似乎类似于FFT算法，但我仍然看不到解决方案。很乐意得到一些帮助！甚至只是一种思考的方式。
请注意，不应提供任何代码。。只有关于如何完成它的解释，也许还有伪代码。
谢谢！
以下是一些提示，然后是解决方案。
1-首先，你应该确保你可以在小于n^2的系数乘法中执行乘法，举个简单的例子：
（aX+b）*（cX+d）
你的一个乘法应该是（a+b）*（c+d）
2-还没找到怎么做？以下是每种电源的操作：
X^2：ac
X:（a+b）*（c+d）-ac-bd
1:bd
你只需要执行3次乘法运算，而不是4次。与乘法相比，加法的成本并没有那么高。
3-你被要求在Theta（n^lg（3））中找到一个解决方案。以下是"Théorème Général"的快速提醒：
设T（n）为次数为n的多项式的算法成本。
采用"分而治之的战略"，导致：
T（n）=aT（n/b）+f（n）
如果f（n）~O（n^lg_b（a）），则T（n）=θ
您正在寻找T（n）=Theta（n^lg_2（3））。这可能意味着：
T（n）=3.T（n/2）+ε
如果你把你的多项式分成偶数和奇数多项式，它们有一半的初始系数：n/2。
这个公式告诉你，你将在奇数和偶数多项式之间进行三次乘法。。。
4-考虑以这种方式表示次数为n的多项式P（x）：
p（X）=X.A（X）+B（X）
A（X）和B（X）包含n/2个系数。
5-解决方案
p（X）=X.A（X）+B（X）
p'（X）=X.A'（X
p*p'（X）的系数是的系数之和
X^2.A.A'
X。（A.B'+A'.B）=X.[（A+B）（A'+B'）-A.A'-B.B']
B.B'
所以你必须调用你的乘法算法：
A和A’
A+B和A'+B'
B和B’
然后可以通过移位和加法重新组合系数。
干杯