計算量とは？

詳細解説

計算量（Computational Complexity）は、アルゴリズムの効率性を定量的に評価するための概念です。主に「時間計算量」と「空間計算量」の2種類があります。時間計算量は、入力サイズnに対して必要な基本演算（比較・代入など）の回数の増加傾向を示し、Big-O記法で表します。空間計算量は、アルゴリズムの実行に必要なメモリ量の増加傾向です。計算量の評価には「最悪ケース」「平均ケース」「最良ケース」の3種類があり、一般的に最悪ケースを指すことが多いです。例えば線形探索の最悪計算量はO(n)（探索値が配列末尾にある場合）ですが、最良計算量はO(1)（先頭が探索値の場合）です。FE試験では各アルゴリズムの計算量の大小比較（O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)）と、具体的なアルゴリズム・データ構造との対応を問う問題が出題されます。計算量の理解は、複数の実装案から実用的なものを選ぶエンジニアリング判断の基礎でもあります。

FE試験での出題ポイント

• 1時間計算量と空間計算量の2軸で評価する
• 2最悪/平均/最良ケースの区別（通常は最悪ケースを評価基準とする）
• 3Big-O記法との関係：定数係数・低次項は無視
• 4O(1) < O(log n) < O(n) < O(n log n) < O(n²) の大小順序の記憶

関連用語