基本情報技術者試験の計算量（O記法）を初心者向けに分かりやすく解説します。
O(1)、O(log n)、O(n)、O(n²)の違いや考え方を、線形探索・二分探索・バブルソートを例に図付きで説明します。午前試験対策にも最適です。
計算量とは
プログラムには、処理が終わるまでにかかる時間や手順の数が異なります。
同じ結果を得られるプログラムでも、処理方法によって速さに大きな違いが生じることがあります。
この処理の効率を表す指標が計算量です。
計算量とは何か
計算量とは、プログラムが処理を終えるまでに必要な処理回数や、処理時間を表す指標です。
計算量は同じアルゴリズムでも、データ量によって変化します。
例えば、100人の名簿から特定の人を探す場合と、10,000人の名簿から探す場合では、一般的には10,000人の名簿の方が多くの時間がかかります。
このように、データの件数が増えたときに処理量がどのくらい増えるかを表すのが計算量です。
なぜ計算量を学ぶのか
計算量を学ぶことで、複数のアルゴリズムの中からより効率の良い処理方法を選べるようになります。
例えば、ソートアルゴリズムにはバブルソートやクイックソートなどがありますが、データ数が少ない場合は大きな違いがなくても、データ数が増えると処理時間に大きな差が生じます。
そのため、実際のシステム開発では、目的やデータ量に応じて適切なアルゴリズムを選ぶことが重要です。
オーダー（O記法）とは
計算量を表すときによく使われるのがO記法（オーダー記法）です
O記法は、プログラムが処理するデータの件数が増えたときに、処理時間がどのように増えていくかを表します。
O記法とは
O記法とは、データ数が増えたときの処理時間の増え方を表す方法です。
例で説明します。
- O(1)：データ数が増えても処理時間はほとんど変わらない
- O(n)：データ数に比例して処理時間が増える
- O(n²)：データ数が増えると処理時間が大きく増える
O記法の考え方
例えば、100件のデータを処理するプログラムと、10,000件のデータを処理するプログラムでは、処理時間は大きく変わります。
- O(1) は、データが増えても処理時間はほとんど変わりません。
- O(n) は、データが2倍になると処理時間も約2倍になります。
- O(n²) は、データが2倍になると処理時間は約4倍になります。
定数や係数を無視する理由
O記法では、定数や係数は考えず、一番大きく影響する部分だけを見ます。
例えば、
n² + n
という式があった場合も、データ数が増えるほど n² の影響が大きくなるため、
O(n²)
と表します。
線形探索の計算量
線形探索では、先頭から順番に1人ずつ確認していきます。
例えば、10の配列要素から目的の値を探す場合、最悪10全ての配列要素を確認する必要があります。
データ数を n とすると、確認する回数も最大 n回なので、計算量は以下になります。
O(n)
二分探索の計算量
二分探索では、毎回データを半分に絞り込みます。
下の絵は、1～16まで並んだ数字から「13」を探す例です。
1回探すごとに、探す範囲が半分になります。
16つの真ん中の値を見る ⇒ 発見できなかったので半分の8つの要素に絞る
8つの真ん中の値を見る ⇒ 発見できなかったので半分の4つの要素に絞る
4つの真ん中の値を見る ⇒ 発見できなかったので半分の2つの要素に絞る
2つの真ん中の値を見る ⇒ 発見できなかったので半分の1つ要素に絞る
今度は配列要素の数が2倍の32だった場合は以下のようになります。
32つの真ん中の値を見る ⇒ 発見できなかったので半分の16つの要素に絞る
16つの真ん中の値を見る ⇒ 発見できなかったので半分の8つの要素に絞る
8つの真ん中の値を見る ⇒ 発見できなかったので半分の4つの要素に絞る
4つの真ん中の値を見る ⇒ 発見できなかったので半分の2つの要素に絞る
2つの真ん中の値を見る ⇒ 発見できなかったので半分の1つ要素に絞る
データ件数(配列の要素数)が2倍になっても半分にする回数は1回増えただけです。
下の表のように、データ数が2倍になっても、探索回数は1回しか増えていません。
| データ数 | 半分にする回数 |
|---|---|
| 8件 | 3回 |
| 16件 | 4回 |
| 32件 | 5回 |
| 64件 | 6回 |
log₂は、「2で何回割ると1になるか」を表しています。
16は2で4回割ると1になる
32は2で5回割ると1になる
64は2で6回割ると1になる
つまり、
16 → log₂16 = 4
32 → log₂32 = 5
64 → log₂64 = 6
そのため、二分探索の計算量は
O(log n)
と書きます。
基本情報技術者試験では、「二分探索の計算量はO(log n)」ということだけを覚えておけば良いです。
バブルソートの計算量
バブルソートでは、1周目は n−1 回、2周目は n−2 回…というように比較回数が少しずつ減っていきます。
そのため、比較回数は (n−1)+(n−2)+…+1 となります。
(n−1)+(n−2)+…+1は、高校数学で学ぶ等差数列の和で n(n−1)/2 と表せます。
O記法では細かな係数（1/2）や小さな項（−n）は無視し、データ数が増えたときに最も影響が大きい n² に注目します。そのため、バブルソートの計算量は次のように書きます。
ソートの説明はこちらを参照してください。
O(n²)
腕試し（理解テスト）
腕試し（理解テスト）に挑戦する場合はこちらをクリック。
コメント