本の後ろに記載されているこの問題に少し問題があります。現在、テスト準備の最中ですが、本でこれに関するものを見つけることができないようです.
誰でもアイデアを得ましたか？
A real polynomial of degree n is a function of the form f(x)=a(n)x^n+⋯+a1x+a0, where an,…,a1,a0 are real numbers. In computational situations, such a polynomial is represented by a sequence of its coefficients (a0,a1,…,an). Assuming that any two real numbers can be added/multiplied in O(1) time, design an o(n^2)-time algorithm to compute, given two real polynomials f(x) and g(x) both of degree n, the product h(x)=f(x)g(x). Your algorithm should **not** be based on the Fast Fourier Transform (FFT) technique.
small-o(n^2) である必要があることに注意してください。つまり、その複雑さは二次以下でなければなりません。
私が見つけてきた明らかな解決策は確かにFFTですが、もちろんそれを使用することはできません。私が見つけた畳み込みと呼ばれる別の方法があります。ここでは、多項式 A を信号とし、多項式 B をフィルタとする場合です。A が B を通過すると、A によって「平滑化」されたシフト信号が生成され、その結果は A*B になります。これは O(n log n) 時間で動作するはずです。もちろん、私は実装について完全に確信が持てません。
small-o(n^2) の実装を実現する方法について誰かがアイデアを持っている場合は、共有してください。