
【情報の基礎理論】1.4 データ構造とアルゴリズム
1. はじめに:整理整頓の重要性
本棚の本を「買った順」に並べるか、「作者順」に並べるか、「ジャンル順」に並べるか。
これによって、「読みたい本を探すスピード」 が劇的に変わりますよね?
コンピュータも同じです。大量のデータをメモリ上でどう並べて管理するか(データ構造)によって、処理速度(アルゴリズムの効率)が天と地ほど変わります。
「プログラムが遅い!」というトラブルの多くは、このデータ構造の選び間違いが原因です。
2. 基本データ構造

スタック (Stack)
仕組み: 最後に積んだものを最初に取り出す (LIFO: Last In, First Out)。
例え話: 社内食堂の「お盆」。洗ったお盆は積み上げられ、次に使う人は一番上の(最後に置かれた)お盆を取ります。
用途: ブラウザの「戻る」ボタン、エディタの「Undo(元に戻す)」機能。
キュー (Queue)
仕組み: 最初に並んだものが最初に取り出される (FIFO: First In, First Out)。
例え話: 人気ラーメン店の「行列」。先に来た人から順に案内されます。
用途: プリンタの印刷待ち行列(印刷ジョブ)、チャットのメッセージ送信順序。
木構造 (Tree)
仕組み: 根(Root)から枝分かれして広がる階層構造。
例え話: 会社の「組織図」、パソコンの「フォルダ構成」。
メリット: 階層化されているため、目的のデータにたどり着くまでの探索回数が少なくて済みます。

3. アルゴリズム(整列と探索)
データ構造が決まれば、それを扱う手順(アルゴリズム)が決まります。
ここでは「探す」ことに焦点を当ててみましょう。
線形探索 (Linear Search)
やり方: 端から順番に一つずつ確認する。
例え: 散らかった机の上から特定の書類を探す。
性能: データ量が2倍になれば、探す手間も2倍になる。遅い。
二分探索 (Binary Search)
やり方: (整列済みのデータに対して)真ん中のデータを見て、探しているものがそれより大きいか小さいかで、探索範囲を半分、また半分と絞り込む。
例え: 数当てゲーム(Hi-Loゲーム)。「1〜100の数字を当てて」と言われたら、まず「50?」と聞きますよね?
性能: データ量が2倍になっても、探す手間は「1回」しか増えない。爆速。
💡 TIP 実務への教訓
「二分探索を使いたい」なら、データは事前に「整列(ソート)」されている必要があります。
「整理整頓(ソート)しておけば、後で探す(サーチ)のが楽になる」
これはプログラミングだけでなく、業務効率化の鉄則でもあります。
4. 演習:アルゴリズムの効率
Q1. 探索回数の比較
データが 1,000個 あるリストから、特定の人を探したいとします。
線形探索:最悪の場合、何回チェックする必要がありますか?
二分探索:最悪の場合、約何回チェックすれば見つかりますか?(2^10 = 1024 です)
・
・
・
▼ 解答と解説
答え
線形探索:1,000回
運が悪ければ、リストの一番最後にあるかもしれません。全員に聞く必要があります。二分探索:約10回
1回確認するたびに候補が半分になります。
1000 → 500 → 250 → 125 → 62 → 31 → 16 → 8 → 4 → 2 → 1
たった10回の確認で見つかります。
もしデータが 100万個 になったら?
線形探索:100万回
二分探索:約20回 (2^20 ≒ 1,000,000)
この圧倒的な差が、大規模システム(Google検索やデータベース)の裏側を支えています。