仕上げは 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記法のどこに位置するか」 を毎回意識する、 という流れが効くと思います。