0

在即将到来的考试中寻求一些帮助,这是来自评论的一个问题。看看是否有人可以重述 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 的幂。

4

1 回答 1

0

这是我找到的进行多项式乘法的链接。

http://algorithm.cs.nthu.edu.tw/~course/Extra_Info/Divide%20and%20Conquer_supplement.pdf

请注意,如果我们按照高中学习的方式进行多项式乘法,则需要大欧米伽(n^2)时间。这个问题想让你看到有一个更有效的算法,首先预处理多项式,把它分成两部分。本讲座对如何执行此操作进行了非常详细的解释。特别是,请查看链接的第 12 页。它明确地向您展示了在多项式相乘时如何在 3 中完成 4 乘法过程。

于 2012-11-27T22:55:45.430 回答