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

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

提供: kimoto's wiki

2013年7月24日 (水) 05:49時点におけるKimoto (トーク | 投稿記録)による版

(差分) ←前の版 | 最新版 (差分) | 次の版→ (差分)

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