初心者でもわかる！アルゴリズム入門
～探索・再帰・計算量をやさしく理解しよう～
プログラミングを勉強していると、
- クイックソート
- 線形探索
- ハッシュ法
- 二分探索
- 再帰
- オーダー（計算量）
など、聞き慣れない言葉がたくさん出てきます。
「難しそう…」「暗記するしかないのかな？」
と思うかもしれません。
しかし、実はそれぞれにきちんと意味があります。
この記事では、基本情報技術者試験でも頻出のアルゴリズムを、IT初心者向けにできるだけやさしく解説します。
まずは全体像を見てみましょう
この記事では、この7つのアルゴリズムを順番に学んでいきます。
アルゴリズムとは？
アルゴリズムとは、
問題を解決するための手順
のことです。
例えば料理なら、
- 野菜を切る
- 炒める
- 味付けする
という手順があります。
プログラムでも同じように、
「どのような順番で処理するか」
を決めています。
ソートと探索の違い
アルゴリズムにはさまざまな種類がありますが、大きく分けると次の2つがあります。
- ソート（並べ替え）
- 探索（探す）
例えば本棚を考えてみましょう。
本がバラバラに置かれていると、目的の本を探すのは大変です。
そこで、まず五十音順やジャンルごとに並べ替えておけば、探しやすくなります。
プログラムでも同じです。
まずデータを並べ替え（ソート）、その後に目的のデータを探す（探索）ことで、効率よく処理できます。
① クイックソート
ソートとは、
データを順番に並べ替えること
です。
例えば
3 5 8 7 6 4 2 1 9を
1 2 3 4 5 6 7 8 9に並べ替えたいとします。
クイックソートでは、まず基準値（ピボット）を決めます。
その値より
- 小さいグループ
- 大きいグループ
に分け、それぞれをさらに同じ方法で分けていきます。
ポイント
クイックソートは、
「分けながら並べるアルゴリズム」
です。
② 線形探索
探索とは、
目的のデータを探すこと
です。
線形探索は、
先頭から順番に調べます。
例えば
5 → 3 → 8 → 1 → 6なら、
6が見つかるまで1つずつ比較します。
特徴
メリット
- 実装が簡単
デメリット
- データが増えるほど時間がかかる
③ ハッシュ法
ハッシュ法は、
計算によって保存場所を決める方法
です。
例えば
32 mod 10 = 2なら、
最初から2番地を見れば目的のデータがあります。
全部探す必要がないので、
非常に高速です。
④ ハッシュ法の弱点（衝突）
便利なハッシュ法にも弱点があります。
異なるデータでも同じ場所になることがあります。
例えば
32 mod 10 = 2
42 mod 10 = 2どちらも2番地になります。
これを
衝突（Collision）
といいます。
試験でもよく問われるポイントです。
⑤ 二分探索
二分探索は、
真ん中を見て半分ずつ範囲を狭める探索方法
です。
ただし、
データがあらかじめ昇順（または降順）に並んでいること
が条件になります。
例えば
1 2 3 4 5 6 7 8 9から6を探すと、
まず中央の5を調べます。
6の方が大きいので左半分を捨てます。
次に中央の7を調べます。
6の方が小さいので右半分を捨てます。
すると6だけが残り、見つかります。
二分探索は「ソートが終わったデータ」に対して行う探索方法です。
データがバラバラなら、まずソートしてから二分探索を行います。
⑥ 再帰アルゴリズム
再帰とは、
自分自身を呼び出す処理
です。
例えば
1 + 2 + 3 + 4 + 5なら
5 + (1～4)
↓
5 + 4 + (1～3)
↓
5 + 4 + 3 + (1～2)
↓
・・・
↓
15というように、
自分自身を呼び出しながら計算します。
重要なのは、
必ず終了条件があることです。
終了条件がなければ、
処理は終わりません。
⑦ オーダー（計算量）
アルゴリズムには、
「どれくらい時間がかかるか」
という目安があります。
これを
オーダー（計算量）
といいます。
記号は
O(…)で表します。
代表的なものは次のとおりです。
| アルゴリズム | 計算量 | 100万件の例 |
|---|---|---|
| ハッシュ法 | O(1) | 約1回（ハッシュ表作成済み） |
| 二分探索 | O(log n) | 約20回（整列済みデータ） |
| 線形探索 | O(n) | 最大100万回 |
| クイックソート | O(n log n) | 約2,000万回程度（並べ替え） |
ここで注意したいのは、
二分探索はソート済みデータに対して使う探索方法であることです。
そのため、最初の1回だけはソートの時間が必要になります。
しかし、一度並べ替えてしまえば、その後は何度検索しても高速に探せるようになります。
まとめ
アルゴリズムは最初は難しく感じますが、
- クイックソート：分けながら並べる
- 線形探索：最初から順番に探す
- ハッシュ法：計算で保存場所を決める
- ハッシュ法の弱点：衝突が起こることがある
- 二分探索：ソート済みデータを半分ずつ探す
- 再帰：自分自身を呼び出す
- オーダー：処理時間の目安
というイメージを持てば理解しやすくなります。
基本情報技術者試験では、単に名称を覚えるだけではなく、
「なぜそのアルゴリズムが速いのか」
「どんな条件で使えるのか」
まで理解しておくと、応用問題にも対応しやすくなります。