「O(n)って何？」から理解しよう！基本情報技術者試験のオーダー記法を初学者向けに解説
基本情報技術者試験では、
- O(1)
- O(log n)
- O(n)
- O(n log n)
といったオーダー記法がよく登場します。
しかし、多くの初学者は
「そもそも O(n) の意味が分からない…」
というところで止まってしまいます。
実は、私も授業では最初から O(n) という言葉は使いません。
まずは、
「何回調べることになるの？」
という考え方から説明します。
O(n)を忘れて、「何回見るか」を考えよう
教室に30人いるとします。
その中から「田中さん」を探します。
方法① 最初から順番に探す
①
②
③
④
⑤
…
30田中さんが最後だったら
30人全員見ることになります。
人数が増えると？
今度は100人になりました。
30人 → 最大30回調べる
100人 → 最大100回調べる
1000人 → 最大1000回調べるつまり、
人数が増えるほど、調べる回数も同じように増えていきます。
ここで初めて「n」が登場します
数学では、
データの個数
を
nという文字で表します。
例えば
10人なら n=10
100人なら n=100
1000人なら n=1000です。
つまり
最大 n 回調べるということになります。
O(n)って何？
ここで
O(n)が登場します。
この
Oは
Order（オーダー）
の頭文字です。
意味としては
「データ数が増えたとき、処理時間がどのように増えるか」
を表しています。
つまり
O(n)
↓
データ数と同じくらい処理回数が増えるという意味なのです。
O(1)はどういう意味？
今度は辞書を考えてみます。
住所録に
田中さん
→ 18ページと書いてあります。
すると
18ページを開くだけで見つかります。
データが
100件
1000件
100万件になっても
見る場所は
1か所だけです。
つまり
O(1)になります。
O(log n)はどういう意味？
次は二分探索です。
100万人の名簿があります。
最初から探すのではなく、
真ん中
を見ます。
100万人
↓
50万人
↓
25万人
↓
12万人
↓
…と、
毎回半分になります。
例えば1024件なら
1024
↓
512
↓
256
↓
128
↓
64
↓
32
↓
16
↓
8
↓
4
↓
2
↓
1これで
10回
しか見ません。
1000件以上あるのに
10回程度で済むのです。
これが
O(log n)です。
ここで数学の登場です。
二分探索は、
「何回半分にすると1になるか」
を考えています。
つまり、
100 ÷ 2 ÷ 2 ÷ 2 ÷ 2 ÷ 2 ÷ 2 ≒ 1です。
これは、
2を何回掛けると100になるか？という問題と同じです。
数学では、
「2を何回掛けるか」
を
と書きます。
読み方は、
2を底とする100の対数
です。
計算すると、
6.64回ってどういう意味？
実際には、
6.64回探すわけではありません。
探索回数は整数なので、
6回では足りない
↓
7回必要となります。
だから、
↓
約7回
と考えます。
線形探索・二分探索・ハッシュ探索を比較してみよう
この表を見るだけでも、
アルゴリズムによって処理回数が大きく違う
ことが分かります。
基本情報試験ではここだけ覚えよう
| 探索方法 | 意味 | オーダー |
|---|---|---|
| 線形探索 | 最初から順番に探す | O(n) |
| 二分探索 | 毎回半分にする | O(log n) |
| ハッシュ探索 | 直接探しに行く | O(1) |
ここでは、
Oの式を暗記するよりも、何回調べるかをイメージできること
の方が大切です。
まとめ
基本情報技術者試験では、オーダー記法が苦手な受験者は少なくありません。
しかし、
- 「何回調べるのか？」
- 「データが10倍になったら、処理回数も10倍になるのか？」
- 「半分ずつ減るのか？」
- 「最初から場所が分かっているのか？」
という視点で考えると、自然に理解できるようになります。
O(n)は難しい数式ではありません。
「データが増えたときの処理回数の増え方」を表すラベルだと考えれば、基本情報技術者試験の探索アルゴリズムはぐっと理解しやすくなります。