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

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

提供: kimoto's wiki

2013年7月24日 (水) 05:49時点におけるKimoto (トーク | 投稿記録)による版 (ページの作成:「*普通に行列積を計算するとΘ(n^3)の実行時間がかかる *単純な分割統治アルゴリズムでこれを計算しても、Θ(n^3)の実行時間がか...」)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)

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