0

次の推論に何か問題があることは知っていますが、それが何であるかはわかりません。

FFT:

  1. 与えられた 2 つの多項式

    A = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n

    と

    B = b_0 + b_1 x + b_2 x^2 + ... + b_n x^n

    積の係数を計算できます

    AB = \sum _k = 0 ^ 2n ( \sum _ j = 0 ^ k (a_j b_{k-j}))x^k

    間に合いO(n log n )ます。

  2. したがって、2 つのベクトルが与えられた場合、時間内にベクトルを(a_0, ..., a_n)計算(b_0, ..., b_n)できます(ベクトルをゼロに埋め込むことによって)。v_i = \sum j = 0 ^ k ( a_j b_{k-j})O(n log n)

  3. 上記を考えると、ベクトルの 1 つを前処理し、時間内に 2. のように畳み込みを計算することによって、A =(a_0, ..., a_n)との内積を計算できるはずです。B =(b_0, ..., b_n)A.B = \sum_j=0 ^ n a_j b_jO(n log n)BB' = (b_n, b_{n-1}, ..., b_1, b_0)O(n log n)

上記の推論が正しければ、時間内の内積を計算することで、2 つの行列の行列乗算を時間内に実装できることを意味しnxnます。O(n^2 log n )O(n log n)O(n)

ただし、私たちが知っている行列乗算の最適な実行時間は約でO(n^2.4)あるため、これが真実である可能性は低いと思われます。これは、おそらくステップ 1、2、または 3 の意味が正しくありません。

4

2 に答える 2

4

製品にはn^2エントリがありますが、そうではないnため、このアルゴリズムはになりますO(n^2 * n * log n) = O(n^3 log n)。

そして、内積を計算するための最良のアルゴリズムはO(n)、ではなくO(n log n)です。そのため、行列乗算の単純なアルゴリズムはですO(n^3)。（時間n^2内に実行できるのはドット積ですO(n)）。

于 2009-11-12T19:23:35.527 に答える
2

ドット積はO（n）時間で計算できることがよく知られているのに、ステップ3でドット積をO（n log n）時間で計算できるのはなぜ達成なのだろうか。また、ステップ2はO（n log n）ステップではなく線形時間のように見えますか？

また、O（n ^ 2 log n）に関する結論は論理的には続きません。ドット積をO（n）回取得して、AB行列を作成することはできません---私が知る限り、O（n ^ 2）ドット積を取得する必要があり、（分析によれば）O（n ^ 3 log n）これは標準のO（n ^ 3）より劣っています。これは、奇妙なO（n log n）内積の結果が原因です。

于 2009-11-12T19:24:47.633 に答える