計算量（オーダー記法）とは？

計算量（オーダー記法）の意味

アルゴリズムの実行時間や必要な記憶容量が、データ件数nの増加に対してどのように増えていくかを表す記法。O(1)（定数時間）、O(log n)、O(n)、O(n log n)、O(n²)などの階級で表され、値が小さいほど大規模データに強い。

計算量（オーダー記法）の具体例

線形探索はO(n)、二分探索はO(log n)であり、データ件数が100万件になったとき、二分探索の比較回数（約20回）は線形探索（最大100万回）と比べ桁違いに少なくなる。

計算量（オーダー記法）は試験でどう引っ掛けられる？

「O(n²)は常にO(n log n)より遅い」とは限らない（データ件数が小さいうちは定数項の影響で逆転することがある）が、試験ではオーダーの大小関係の理解が主に問われる。

計算量（オーダー記法）と関連する用語

• 整列アルゴリズムの計算量
• 二分探索法と線形探索法

計算量（オーダー記法）が出た過去問

• クラウドで学習し，エッジデバイスで推論する機械学習ベースのエッジAIにおいて，エッジデバイスで行われる推論処理として，適切なものはどれか。

  正解：学習したモデルに従い，実際にデータの識別などを行うプロセス

  要点：エッジAIは学習をクラウド、推論を機器側で行う役割分担

  機械学習は、データからモデルを作る学習（訓練）と、できたモデルに新しいデータを入れて判断させる推論の2段階に分かれる。エッジAIでは計算量の大きい学習をクラウドで行い、出来上がったモデルを機器側に配置して推論だけを実行する。これにより通信遅延を抑え、現場で即座に識別や判定ができる。

  出典：令和7年度 春期 応用情報技術者試験 午前 問71（IPA）

• ヒープソートの説明として、適切なものはどれか。

  正解：未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して、未整列の部分を縮めていく。

  要点：ヒープソートは順序木の根から極値を取り出して整列する

  ヒープソートは、未整列部分をヒープ（親子間に大小関係が保たれた順序木）として構成し、根にある最小値または最大値を取り出して整列済み部分へ移す操作を繰り返す方式です。取り出すたびにヒープを再構成するため、計算量は要素数nに対しておおむね n log n となります。他の選択肢はシェルソート、クイックソート、バブルソートの説明です。

  出典：平成28年度 秋期 応用情報技術者試験 午前 問6（IPA）

• ポインタを用いた線形リストの特徴のうち、適切なものはどれか。

  正解：ポインタによって指定されている要素の後ろに、新たな要素を追加する計算量は、要素の個数や位置によらず一定である。

  要点：線形リストの挿入・削除はポインタ操作だけで一定時間

  ポインタで連結された線形リストは、要素の追加・削除がポインタの張り替えだけで済む。挿入位置がポインタで指定されていれば、要素数や位置に関係なく一定の手間（計算量O(1)）で挿入できる。一方、任意の要素へアクセスするには先頭から順にたどる必要がある。

  出典：令和2年度 10月 応用情報技術者試験 午前 問5（IPA）

• バブルソートの説明として、適切なものはどれか。

  正解：隣り合う要素を比較して、大小の順が逆であれば、それらの要素を入れ替えるという操作を繰り返す。

  要点：バブルソートは隣接要素の比較交換を繰り返す整列法

  バブルソートは隣り合う要素を順に比較し、大小の順序が逆であれば交換する操作を繰り返す整列法である。1回の走査で最大値（または最小値）が端に移動する様子が泡の浮上に似ることから、この名で呼ばれる。実装は単純だが計算量はO(n^2)で、大量データには向かない。

  出典：令和3年度 秋期 応用情報技術者試験 午前 問5（IPA）

• コンピュータグラフィックスに関する記述のうち、適切なものはどれか。

  正解：ラジオシティ法は、拡散反射面間の相互反射による効果を考慮して拡散反射面の輝度を決める。

  要点：ラジオシティ法は拡散面どうしの相互反射で輝度を求める

  ラジオシティ法は、拡散反射する面どうしが互いに光を反射し合う影響（相互反射）を計算して各面の輝度を求める大域照明の手法である。柔らかな間接光や色移りを表現できる一方、計算量が大きい。他の選択肢は用語と説明の組合せが入れ替えられている。

  出典：令和3年度 秋期 応用情報技術者試験 午前 問25（IPA）