メインコンテンツへスキップ
見出し画像

【情報の基礎理論】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個 あるリストから、特定の人を探したいとします。

    1. 線形探索:最悪の場合、何回チェックする必要がありますか?

    2. 二分探索:最悪の場合、約何回チェックすれば見つかりますか?(2^10 = 1024 です)

    ・
    ・
    ・

    ▼ 解答と解説

    答え

    1. 線形探索:1,000回
      運が悪ければ、リストの一番最後にあるかもしれません。全員に聞く必要があります。

    2. 二分探索:約10回
      1回確認するたびに候補が半分になります。
      1000 → 500 → 250 → 125 → 62 → 31 → 16 → 8 → 4 → 2 → 1
      たった10回の確認で見つかります。

    もしデータが 100万個 になったら?

    • 線形探索:100万回

    • 二分探索:約20回 (2^20 ≒ 1,000,000)

    この圧倒的な差が、大規模システム(Google検索やデータベース)の裏側を支えています。


     
     
    ITインストラクター、ITエンジニア、AIエンジニアなどのお仕事で生計を立てている猫です。おいしいご飯が大好きです。お好きに閲覧してやってくださいませ。いいねしてくれるととても喜びます😽