O記法

Big O Notation おーきほう

最頻出 ⚪ 旧用語テクノロジ系基礎理論

意味・解説

アルゴリズムの計算量を、入力サイズnに対する増加の度合いで表す記法。

最悪ケースでの計算量の上界を表す。O(1)は定数時間、O(n)は線形、O(n²)は2乗、O(log n)は対数時間を示す。係数や低次の項は省略する。

データが増えたときに、処理時間がどれくらい増えるかを表す指標です。

【代表的な計算量】

・O(1): 配列の添字アクセス

・O(log n): 2分探索

・O(n): 線形探索

・O(n²): バブルソート

バブルソートの時間計算量はO(n²)であり、データ量が10倍になると処理時間は約100倍になる。

同義語: ビッグオー記法, オーダー記法

分類: 計算複雑性理論