最終更新日：2026年9月20日
fe fe-technology algorithm
まず結論
複数の処理区分を順番に比較して判定する場合は、出現確率が高いものを先に判定するほど、平均比較回数を少なくできます。
試験では、次の形を覚えておくと判断しやすくなります。
よく出る処理
→ 少ない比較回数で判定
あまり出ない処理
→ 比較回数が多くても全体への影響は小さい
つまり、
「よく出るものを浅い位置に置く」
のが基本です。
直感的な説明
3種類の処理があり、出現比率が次のようだったとします。
| 処理区分 | 出現比率 |
|---|---|
| A | 60% |
| B | 30% |
| C | 10% |
Aを最初に判定すると、
A → 1回で判定
B → 2回で判定
C → 2回で判定
となります。
平均比較回数は、
1×0.6 + 2×0.3 + 2×0.1
= 1.4回
です。
一方、最も少ないCを最初にすると、
C → 1回
A → 2回
B → 2回
なので、
1×0.1 + 2×0.9
= 1.9回
になります。
出現比率が高いものを早く判定できるようにすると、全体の平均比較回数が減ることが分かります。
定義・仕組み
平均比較回数は、各処理区分が判定されるまでに必要な比較回数を、出現確率で重み付けして平均したものです。
考え方は期待値と同じです。
平均比較回数
= Σ（その処理の比較回数 × 出現確率）
3種類を順番に判定する場合
たとえば、処理A・B・Cを順に判定するとします。
最初にAを判定すると、
Aか？
├─ Yes → A
└─ No
└─ Bか？
├─ Yes → B
└─ No → C
比較回数は、
| 処理 | 比較回数 |
|---|---|
| A | 1回 |
| B | 2回 |
| C | 2回 |
となります。
そのため、Aの出現確率が高いほど平均比較回数は小さくなります。
試験での判断基準
問題文に次のような表現があれば、この考え方を疑います。
- 処理区分ごとの出現比率が分かっている
- 比較回数を少なくしたい
- 条件判定の順番を決めたい
- 平均処理時間を短くしたい
この場合、
出現確率が最も高いものを、できるだけ少ない判定回数で確定させる
と考えます。
どんな場面で使う？
この考え方は、条件分岐の判定順を工夫するときに使います。
例えば、
if 最も多いケース:
処理A
elif 次に多いケース:
処理B
else:
処理C
のように、出現頻度の高いケースを前に置けば、多くのデータを少ない比較回数で処理できます。
また、考え方としては次のような分野にもつながります。
- 探索処理
- 決定木
- ハフマン符号
- 分岐処理の最適化
共通しているのは、
頻度の高いものに短い経路を割り当てる
という考え方です。
よくある誤解・混同
「真ん中の頻度を最初にすればバランスがよい」ではない
平均比較回数を最小にしたい場合、単純に中央の頻度を選ぶわけではありません。
重要なのは、
出現比率 × 比較回数
です。
頻度の高い処理を少ない比較回数で済ませる方が、平均値を下げやすくなります。
「最も少ない処理から判定する」と逆効果になりやすい
最も少ない処理を最初にすると、その少数だけは1回で判定できます。
しかし、残りの大部分が2回以上の比較を必要とするため、平均比較回数は増えやすくなります。
「判定順は関係ない」ではない
2種類だけなら、どちらを先に比較しても1回で決まる場合があります。
しかし3種類以上を順に判定する場合は、どの処理を先に置くかで平均比較回数が変わります。
ここは試験でひっかけやすいポイントです。
「出現比率」ではなく「値の大小」で並べるわけではない
処理区分の番号や値の大小ではなく、
どの区分がどれだけ頻繁に現れるか
を見ます。
確認問題（基本情報技術者試験対策）
3種類の処理A、B、Cの出現比率が、それぞれ70%、20%、10%である。
処理区分を順番に比較して判定するとき、平均比較回数を少なくするために最初に判定する処理として最も適切なものはどれか。
- A
- B
- C
- どれを最初にしても同じ
▶ クリックして答えと解説を見る（ここを開く）
正解：1
Aを最初にすると、
A → 1回
B → 2回
C → 2回
平均比較回数は、
1×0.7 + 2×0.2 + 2×0.1
= 1.3回
です。
最も出現比率の高いAを1回で判定できるため、平均比較回数を最も小さくできます。
まとめ（試験直前用）
- 出現確率が高いものを先に判定する
- 平均比較回数は 比較回数 × 出現確率 の合計で考える
- 3種類以上では、判定順によって平均比較回数が変わる
- 「よく出るものほど浅い位置に置く」と覚える
- ハフマン符号や決定木にも通じる考え方