計算量（オーダ記法）

読み: けいさんりょう / 英語: Time Complexity (Big-O Notation)

概要

アルゴリズムの効率を表す指標。入力サイズnに対する処理時間の増加率を表す。

詳細解説

計算量はアルゴリズムの性能を比較する基本指標です。

主な計算量（小さい順）

表記	名称	例
O(1)	定数時間	配列のインデックスアクセス
O(log n)	対数時間	二分探索
O(n)	線形時間	線形探索
O(n log n)	準線形時間	クイックソート
O(n²)	二乗時間	バブルソート
O(2ⁿ)	指数時間	全探索

最悪計算量と平均計算量

• 最悪計算量: 最も時間がかかる場合
• 平均計算量: 典型的な入力での期待値
• クイックソートは平均O(n log n)だが最悪O(n²)

---

この記事は「計算量（オーダ記法）」についての用語解説です。学習の参考にしてください。