今後の試験の助けを求めて、これはレビューからの質問です。誰かが a) を言い換えることができるかどうかを確認することで、それが何を求めているのかをよりよく理解できるかもしれません。
したがって、余分な乗算を使用する代わりに、既に乗算された項を減算および加算することにより、答え (PQ) の項の一部を取得することを望んでいます。Strassen が彼のアルゴリズムで 2x2 行列の積を 8 回ではなく 7 回の乗算で計算するのと同じように。
a) P(x) と Q(x) が (偶数) サイズ n の 2 つの多項式であると仮定します。
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 の 2 つの多項式を乗算するための分割統治アルゴリズムを設計する方法を簡単に説明してください (再帰呼び出しとは何か、ブートストラップ条件とは何かを説明してください)。
c) パート b) で与えられたアルゴリズムの最悪の場合の複雑さを分析します。具体的には、W(n) の漸化式を導出して解きます。いつものように、計算を簡単にするために、n は 2 の累乗であると仮定できます。