仕上げは AI との協働でやっています。事実と表現は著者本人が確認しています。

ITパスポートのアルゴリズム章でいちばん詰まる場所はどこかと聞かれたら、計算量 (O記法) です。 O(1) と O(n) と O(n²) の違いを覚えさせられても、設問で「以下のうちもっとも効率が良いものは?」と聞かれた時に、受講者の手が止まることが多いです。

数式の話ではあるのですが、「データ件数が増えた時に何倍になるか」という体感がないと、試験当日に選択肢の前で止まります。今回は研修で受講者がよく持ってくる質問を Q&A 形式で潰していきます。

Q1: そもそも O記法って何を表しているのか

A: データ件数が増えた時に、処理時間がどのくらいの伸び方をするか を表しています。

絶対値ではなく「伸び方」を見るのがポイントです。件数が 10 倍になった時に処理時間が何倍になるか、で考えると以下になります。

記法	10件	100件 (10倍)	1000件 (100倍)	伸び方
O(1)	1	1	1	件数に関係なく定数
O(log n)	約3	約7	約10	件数が10倍でも数倍程度
O(n)	10	100	1000	件数と同じ伸び
O(n log n)	約30	約700	約10000	件数の伸び × log
O(n²)	100	10000	1000000	件数の2乗
O(2ⁿ)	1024	天文学的	計算不能	1件増えるごとに2倍

O(1) と O(n²) では、 1000件のデータで処理時間が 100万倍違うことになります。これが「効率の差」の正体です。

Q2: 線形探索と二分探索、何が違うのか

A: 探し方の手順が違うので、計算量が変わります。

線形探索 (Linear Search) は、配列の先頭から1つずつ見ていく方法です。

配列: [3, 7, 12, 18, 25, 33, 41, 50]
目的: 25 を探す

7番目で見つかる
→ 最悪の場合 8回見る必要がある (= データ件数 n に比例)
→ O(n)

二分探索 (Binary Search) は、ソート済みの配列の真ん中を見て、目的の値より大きいか小さいかで半分に絞り込む方法です。

配列: [3, 7, 12, 18, 25, 33, 41, 50] (ソート済み)
目的: 25 を探す

1回目: 真ん中 = 18 → 25 はそれより大きいので右半分 [25, 33, 41, 50]
2回目: 真ん中 = 33 → 25 はそれより小さいので左半分 [25]
3回目: 25 を発見

3回で済む。 件数が倍になっても、 1回多く見るだけで済む
→ O(log n)

8件のデータで 8回 vs 3回。 1000件のデータだと 1000回 vs 10回。件数が増えるほど、二分探索の優位性が圧倒的になります。

ただし二分探索には データがソート済みであること という前提があります。ソートにかかる時間 (O(n log n)) を含めると、 1回しか探さない場合は線形探索の方が速い、ということもあり得ます。何回探すかで判断する、という視点も持っておくと実務でも使えます。

Q3: バブルソート・選択ソート・マージソートの違い

A: 並び替えの考え方が違います。計算量と一緒に押さえます。

バブルソート (Bubble Sort)

隣り合う2つを見て、 順序が逆なら入れ替える、 を繰り返す。
パスを n 回繰り返すと、 1回のパスで n 回比較するので、 n × n = n² の比較が必要。
→ O(n²)

選択ソート (Selection Sort)

未ソート部分の最小値を探して、 先頭と入れ替える、 を繰り返す。
最小値を探すのに n 回、 これを n 回繰り返すので n²。
→ O(n²)

マージソート (Merge Sort)

配列を半分ずつに分けて、 それぞれをソートしてから併合する。
分割の段階で log n 段、 各段でデータ全体 (n) を見るので n × log n。
→ O(n log n)

1000件のデータでざっくり比較すると、バブル・選択ソートは100万回くらいの比較、マージソートは1万回くらいの比較で済みます。 100倍の差が出ます。

試験では「もっとも効率が良いソートはどれか」と聞かれた時、 O(n log n) のソートを選ぶ で外しません。マージソート・クイックソート・ヒープソートはすべて O(n log n) で、バブル・選択・挿入ソートはすべて O(n²) です。

Q4: 「最悪計算量」と「平均計算量」はどう違うのか

A: データの並びがいちばん悪い場合を見るか、平均的な場合を見るかの違いです。

クイックソートが典型例で、平均計算量は O(n log n) ですが、既にソート済みのデータをクイックソートにかけると、最悪 O(n²) まで悪化することがあります。

ソート	最悪計算量	平均計算量
バブルソート	O(n²)	O(n²)
選択ソート	O(n²)	O(n²)
挿入ソート	O(n²)	O(n²)
マージソート	O(n log n)	O(n log n)
クイックソート	O(n²)	O(n log n)
ヒープソート	O(n log n)	O(n log n)

クイックソートは「平均は速いが、最悪を引くと遅い」という性質を持っています。実装では「pivot をランダムに選ぶ」などの工夫で最悪を引きにくくする手法があるのですが、試験ではここまでは聞かれないことが多いです。「クイックソートの最悪は O(n²)、マージソートは常に O(n log n)」を覚えておけば設問は通せます。

Q5: ハッシュテーブルの O(1) ってどういう意味か

A: ハッシュ関数で直接アクセスする場所が決まるので、件数が増えても探索時間が変わらないという意味です。

データ: ["田中", "山田", "林", ...]
        ↓ ハッシュ関数で変換
バケット位置: ["田中"→ 03, "山田"→ 17, "林"→ 09, ...]

「林」 を探したい
→ ハッシュ関数で 09 が計算される
→ バケット09 に直接アクセスして取り出す
→ 1回のアクセスで完了
→ O(1)

ハッシュテーブルの O(1) は 「ハッシュ衝突が起きない理想状態」 の話で、衝突が頻発すると O(n) まで悪化します。試験ではこの理想状態の話で聞かれるので、「ハッシュテーブル = O(1) で検索できる」で覚えて問題ないです。

実務で触る時には、ハッシュ関数の品質や、衝突時の対処 (Open Addressing / Chaining) も論点になりますが、 ITパスポートの範囲では理想状態の理解で十分です。

Q6: 試験ではどう問われるのか

ITパスポートでは「もっとも効率が良いものはどれか」という形で出ます。過去問パターンを集約すると、こういう形が多いです。

大量のデータの中から特定の値を探すアルゴリズムとして、もっとも効率が良いものはどれか。
ア. 線形探索イ. 二分探索ウ. バブルソートエ. ハッシュ探索

正解はエ. ハッシュ探索 (O(1))、次点はイ. 二分探索 (O(log n))。ただし「ソート済みのデータ」という前提が付いていれば二分探索、「ハッシュ表が用意されていれば」の前提でハッシュ探索、と前提条件で判定する設問もあります。

選択肢の前で迷ったら、 計算量の伸び方を比較する で判定するのが速いです。 O(1) → O(log n) → O(n) → O(n log n) → O(n²) の順で速い、と覚えておくと選択肢でも迷いが減ります。

振り返って

計算量は数式の話で覚えにくいのですが、「データ件数が増えた時に何倍になるか」という体感で押さえると、試験の選択肢でも実務で使う時にも効きます。 100万件のデータをバブルソートで扱おうとすると現実的な時間に終わらない、みたいな感覚を持っていると、実装する前に方針を変えられるようになります。

試験対策としては、上のQ&Aの順序で1回読んで、過去問で似た問題に出会ったら「O記法のどこに位置するか」を毎回意識する、という流れが効くと思います。

参考