注意: このページは最後に更新されてから 1444 日が経過している記事です。 文章が腐敗している可能性があります。その点を考慮した上で確認ください。

行列積のためのStrassenのアルゴリズム

提供: kimoto's wiki

  • 普通に行列積を計算するとΘ(n^3)の実行時間がかかる
  • 単純な分割統治アルゴリズムでこれを計算しても、Θ(n^3)の実行時間がかかる
  • Strassenの少し特殊なアルゴリズムを使うとこれを、Θ(n^lg7)で計算可能
    • 特殊すぎて説明ができない。なるからなるんだなという感じ。