計算量（オーダー記法）とは？けいさんりょう
計算量（オーダー記法）とは、アルゴリズムの実行時間や必要な記憶容量が、データ件数nの増加に対してどう伸びるかを、増加の勢いだけで表す記法。O(1)・O(log n)・O(n)・O(n log n)・O(n²)といった階級で表し、定数倍と低次の項は無視する。応用情報では代表的な探索・整列アルゴリズムのオーダーに加え、最悪の場合と平均の場合の違い（クイックソートは平均O(n log n)・最悪O(n²)）まで問われる。
最終更新：2026-10-06
この語が出る過去問を解く →背景
同じアルゴリズムでも、計算機の速度や実装言語が違えば実測時間は変わる。それでは「どちらの方式を選ぶべきか」を機械や年代をまたいで議論できない。定数倍を切り捨て、件数が増えたときの伸び方だけを取り出せば、環境に依存しない比較ができる——オーダー記法はそのための道具である。件数が10倍・100倍になったとき処理時間が何倍になるか、という形で容量・性能の見積りに直結する。
具体例
線形探索はO(n)、二分探索はO(log n)なので、100万件では比較回数が最大100万回に対して約20回と桁が違う。整列ではバブルソートがO(n²)、クイックソートやマージソートが平均O(n log n)であり、件数が100倍になったときの所要時間の伸びは、前者が約1万倍、後者は約200倍にとどまる。
試験での引っ掛け
オーダーが小さいほうが常に速いとは限らない。定数倍を捨てているため件数が小さいうちは逆転することがあり、実際の整列ライブラリも小さい区間では単純な挿入ソートへ切り替える。またオーダーは最悪・平均・最良で異なり、クイックソートを最悪の場合まで含めて「O(n log n)」と言い切ると誤りになる。
関連用語
出た過去問
出典：令和2年度 10月試験 応用情報技術者試験 午前 問5（IPA）
ポインタを用いた線形リストの特徴のうち、適切なものはどれか。
正解：ポインタによって指定されている要素の後ろに、新たな要素を追加する計算量は、要素の個数や位置によらず一定である。
要点：線形リストの挿入・削除はポインタ操作だけで一定時間
ポインタで連結された線形リストは、要素の追加・削除がポインタの張り替えだけで済む。挿入位置がポインタで指定されていれば、要素数や位置に関係なく一定の手間（計算量O(1)）で挿入できる。一方、任意の要素へアクセスするには先頭から順にたどる必要がある。
出典：令和3年度 春期 応用情報技術者試験 午前 問40（IPA）
暗号学的ハッシュ関数における原像計算困難性、つまり一方向性の性質はどれか。
正解：あるハッシュ値が与えられたとき、そのハッシュ値を出力するメッセージを見つけることが計算量的に困難であるという性質
要点：一方向性はハッシュ値から元のメッセージを求められない性質
原像計算困難性（一方向性）とは、あるハッシュ値が与えられたときに、それを出力する元のメッセージを現実的な計算量では求められないという性質である。この性質があるため、パスワードをハッシュ値で保管しても元のパスワードを逆算されにくい。
出典・参考
公式シラバスの1 基礎理論 ＞ 3. 情報に関する理論 ＞ (8) 計算量に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。