計算量とO記法（オーダ記法）とは？
計算量とO記法（オーダ記法）とは、アルゴリズムの実行時間や必要な記憶領域が、データ件数nの増加に対してどう増えるかを表したもの。O記法では最も影響の大きい項だけを残し、係数や定数項は無視する。FEでは各アルゴリズムのオーダを問う問題が頻出する。
基本情報技術者試験の過去問では4回出題されています（2017年度〜2026年度）。
けいさんりょうとおーきほう
計算量とO記法（オーダ記法）の意味
アルゴリズムの実行時間や必要な記憶領域が、データ件数nの増加に対してどう増えるかを表したもの。O記法では最も影響の大きい項だけを残し、係数や定数項は無視する。FEでは各アルゴリズムのオーダを問う問題が頻出する。
計算量とO記法（オーダ記法）の具体例
処理時間が3n²+5n+100と表せるなら、nが大きいときはn²の項が支配的なのでO(n²)と書く。データが10倍になると処理時間は約100倍になる。O(log n)なら10倍になっても数回分しか増えない。
計算量とO記法（オーダ記法）は試験でどう引っ掛けられる？
O記法は「増え方の傾向」であり、実際の実行時間の大小を直接示すものではない。nが小さければO(n²)のほうがO(n log n)より速いこともある。また空間計算量（記憶領域）と時間計算量を混同しないこと。係数や定数項は無視するので、O(2n)もO(n+5)もどちらもO(n)と表記される点も見落としやすい。
計算量とO記法（オーダ記法）と関連する用語
計算量とO記法（オーダ記法）が出た過去問
非常に大きな数の素因数分解が困難なことを利用した公開鍵暗号方式はどれか。
正解：RSA
要点：RSAの安全性の根拠は巨大な数の素因数分解の困難さ
RSAは、巨大な2つの素数の積を素因数分解するのが計算量的に困難であることを安全性の根拠とする公開鍵暗号方式である。暗号化と署名の両方に使える。離散対数問題に基づくDHやDSA、共通鍵暗号のAESとは根拠となる数学的問題が異なる。
出典：平成29年度 秋期 基本情報技術者試験 午前 問38（IPA）クイックソートの処理方法を説明したものはどれか。
正解：適当な基準値を選び，それよりも小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。
クイックソートは基準値（ピボット）を選び、それより小さい群と大きい群にデータを分割し、各群に同じ処理を再帰的に適用する分割統治法である。平均計算量はO(n log n)となる。
出典：平成30年度 秋期 基本情報技術者試験 午前 問6（IPA）楕円曲線暗号の特徴はどれか。
正解：RSA暗号と比べて、短い鍵長で同レベルの安全性が実現できる。
要点：楕円曲線暗号は短い鍵長でRSA並みの安全性を得る
楕円曲線暗号は楕円曲線上の離散対数問題の困難さを安全性の根拠とする公開鍵暗号方式である。同じ安全性を得るのに必要な鍵の長さがRSAよりずっと短く済むため、計算量と通信量を抑えられる。処理能力の限られるICカードやIoT機器での利用に向いている。
出典：令和1年度 春期 基本情報技術者試験 午前 問39（IPA）クイックソートの処理方法を説明したものはどれか。
正解：適当な基準値を選び，それよりも小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。
要点：クイックソートは枢軸で分割し再帰的に整列する
クイックソートは、基準値（枢軸）を選んでデータを基準値より小さい グループ と大きいグループに分割し、各グループに対して同じ操作を再帰的に繰り返して整列する方法である。分割統治法に基づくため平均的な計算量が小さい。挿入・選択・バブルの各整列法とは考え方が異なる。
出典：令和8年度 （公開問題） 基本情報技術者試験 kamokuA 問2（IPA）
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。