在即将到来的考试中寻求一些帮助,这是来自评论的一个问题。看看是否有人可以重述 a) 以便我能够更好地理解它的要求。
所以它希望我通过减去和添加已经相乘的项来获得答案(PQ)中的一些项,而不是使用额外的乘法。就像 Strassen 在他的算法中所做的那样,用 7 次乘法而不是 8 次计算 2x2 矩阵的乘积。
a) 假设 P(x) 和 Q(x) 是(偶数)大小为 n 的两个多项式。
令 P1(x) 和 P2(x) 表示由 P(x) 的前 n/2 和后 n/2 系数确定的大小为 n/2 的多项式。类似地定义Q1(x)和Q2(x),即P = P1 + x^(n/2)P2。Q = Q1 + x^(n/2) Q2。
展示如何仅使用大小为 n/2 的多项式的 3 个不同乘法来计算乘积 PQ。
b) 简要解释 a) 中的结果如何用于设计一个分治算法,用于将两个大小为 n 的多项式相乘(解释递归调用是什么以及引导条件是什么)。
c) 分析你在 b) 部分给出的算法的最坏情况复杂度。特别是推导出 W(n) 的递推公式并求解。像往常一样,为了简化数学,您可以假设 n 是 2 的幂。