Strassen のアルゴリズムは、n-cubed の通常の行列乗算よりも多項式的に高速です。「多項式で高速」とはどういう意味ですか?
3 に答える
4
あなたの質問は「複雑さ」の理論的概念と関係があります。例として、通常の行列乗算はO（n ^ 3）の複雑さを持っていると言われています。これは、次元 "n"が大きくなるにつれて、アルゴリズムの実行にかかる時間、T（n）が正の定数に関して関数 "n ^ 3"（3次関数）を超えないことが保証されることを意味します。正式には、これは次のことを意味します。
すべてのn>=n_tに対して、T（n）<= c * n ^ 3となるような正のしきい値n_tが存在します。ここで、c>0は定数です。
あなたの場合、Strassenアルゴリズムは複雑さO（n ^ log7）を持っていることが実証されています。log7 = 2.8 <3であるため、nが大きくなるにつれて、Strassenアルゴリズムは従来の乗算アルゴリズムよりも高速に実行されることが保証されます。
補足として、nの値が非常に小さい場合（つまり、上記のn <n_tの場合）、このステートメントは当てはまらない可能性があることに注意してください。
于 2012-08-24T06:38:45.740 に答える
2
複雑なアルゴリズムO(n^3)とO(n^2)両方が多項式です。しかし、2 番目の方が多項式的に高速です。
于 2012-08-24T06:36:35.183 に答える
0
この場合、両方のアルゴリズムに多項式の実行時間があることを意味すると思いますが、Strassen アルゴリズムの方が高速です。
これは、標準が (立方体であっても) 多項式であるためです。
とにかく、「多項式的に高速」という用語は標準的な用語ではないと思います。
于 2012-08-24T06:35:01.147 に答える