kxk行列を乗算するためのStrassenのアルゴリズムのこの分析を理解しようとしています。しかし、いくつの操作が関与しているのかはまだよくわかりません。誰かがこれを明確にするのを助けることができますか?
2 に答える
2
実行される操作の数は、次のように決定されます。まず、行列を k/2 のサイズの 4 つの部分試行に分割し、それらの行列の 7 つの再帰的乗算を実行します。次に、これらの製品を一定数追加して、目的の結果を取得します。これにより、次のように定義された再帰関係が得られます。
T(1) = 1
T(k) = 7T(k/2) + ck 2
lg 7 > lg 4 = 2 であるため、lg 7 > 2 であることに注意してください (ここで、lg は 2 進対数です)。したがって、マスター定理のケース 1 により、アルゴリズムの漸近的な複雑さは O(k lg 7 ) ≈ O(k 2.807 ) になります。
お役に立てれば！
于 2011-03-23T20:42:34.343 に答える
0
ページに約 O(N^2.807...) と書かれていることを考えると、これは浮動小数点演算の数の適切な概算になると思います。すべてのループ/反復は整数演算で行われます。
于 2009-10-14T18:36:45.333 に答える