三次時間 O(n³) — 三重ネストループと行列操作
O(n³)三次時間計算量、行列乗算やグラフアルゴリズムで発生する場所、削減戦略について学びます。
Complexity Classes
詳細な説明
O(n³)三次時間とは？
アルゴリズムがO(n³)とは、実行する作業が入力サイズの三乗に比例することを意味します。
代表的なO(n³)アルゴリズム
ナイーブ行列乗算 — 2つのn×n行列を乗算する標準アルゴリズム。
Floyd-Warshallアルゴリズム — 重み付きグラフで全ペアの最短経路を求めます。
LU分解 — 行列を下三角行列と上三角行列に分解します。
より高速な代替手段
- Strassenのアルゴリズム — 行列乗算をO(n²·⁸)に削減
- Johnsonのアルゴリズム — スパースグラフでFloyd-Warshallより高速
- GPUアクセラレーション — 並列化で実用的に対処
ユースケース
三次アルゴリズムは科学計算、グラフ理論、線形代数に現れます。O(n³)の理解は、最適化ライブラリ（BLASなど）や近似アルゴリズムへの切り替え判断に役立ちます。