2

次数 'd' の 2 つの多項式 A と B をそれぞれ乗算しようとしています。これには基本的に 2 つの操作、つまり乗算と加算があります。出力多項式 'C' を得るために必要な演算の総数は? 私はたくさん検索しましたが、乗算の合計は「d ^ 2」になり、加算の合計は「2d-1」になると想定しています。したがって、合計操作は (2d-1)*(d^2) になります。これは本当ですか？または偽？そしてどうやって？提案してください....

4

1 に答える 1

4

次数の多項式にdはd+1係数があります。したがって、単純な実装では(d+1)^2乗算が必要になります。非常に大規模な場合は、 FFTdを使用して操作の数を減らすことができます。O( d log(d))

于 2012-08-13T09:37:56.550 に答える