注意: このページは最後に更新されてから
2838 日が経過している記事です。
文章が腐敗している可能性があります。その点を考慮した上で確認ください。
行列積のためのStrassenのアルゴリズム
提供: kimoto's wiki
- 普通に行列積を計算するとΘ(n^3)の実行時間がかかる
- 単純な分割統治アルゴリズムでこれを計算しても、Θ(n^3)の実行時間がかかる
- Strassenの少し特殊なアルゴリズムを使うとこれを、Θ(n^lg7)で計算可能
- 特殊すぎて説明ができない。なるからなるんだなという感じ。