データ構造とアルゴリズム入門

対象読者: 基本文法を学び、処理の速さやデータの持ち方を理解したい人。

この教材でできるようになること

データ構造とアルゴリズムを区別できる
list、set、mapを用途から選べる
線形探索と二分探索の違いを説明できる
Big Oを厳密な時間ではなく増え方として読める

1. 入れ物と手順を分ける

データ構造: データをどの形で保持するか
アルゴリズム: 目的の結果へ至る手順

同じ検索でも、順不同のlistを先頭から探す場合と、キー付きmapから探す場合では性質が異なります。

2. 基本的なデータ構造

構造	得意なこと	注意点
array/list	順番に並べる、位置で参照	途中挿入や全探索が増えることがある
stack	最後に入れたものから取り出す	LIFO
queue	最初に入れたものから取り出す	FIFO
set	重複排除、存在確認	順序を目的にしない
map/dict	キーから値を探す	キー設計が必要

3. 線形探索

def find_index(values: list[int], target: int) -> int | None:
    for index, value in enumerate(values):
        if value == target:
            return index
    return None

最悪の場合、要素をすべて確認します。要素数をnとすると、処理量の増え方はO(n)です。

4. 二分探索

ソート済みのデータなら、中央との比較で探索範囲を半分ずつ減らせます。

def binary_search(values: list[int], target: int) -> int | None:
    low = 0
    high = len(values) - 1

    while low <= high:
        middle = (low + high) // 2
        if values[middle] == target:
            return middle
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return None

探索範囲が半分ずつになるためO(log n)です。ただし、事前にソート済みであるという条件があります。

5. Big Oの読み方

Big Oは特定PCでの秒数ではなく、入力が増えたとき処理量がどう増えるかを見る尺度です。

記法	増え方の例
`O(1)`	mapのキー検索を平均的に見る
`O(log n)`	二分探索
`O(n)`	全要素を一度見る
`O(n log n)`	効率的な比較ソート
`O(n²)`	全組み合わせを二重loopで比較

小さなデータでは読みやすさを優先できる場合もあります。計測せずに最適化するのではなく、要件、データ量、実測から判断します。

6. 正しさを先に考える

アルゴリズムには少なくとも次を確認します。

空入力
要素が一つ
対象が先頭・中央・末尾
対象がない
重複がある
非常に大きな入力

演習: 重複しない順序付き一覧

入力順を保ちながら、重複した文字列を除外してください。

def unique_in_order(values: list[str]) -> list[str]:
    # 実装する
    ...

解答例

def unique_in_order(values: list[str]) -> list[str]:
    seen: set[str] = set()
    result: list[str] = []
    for value in values:
        if value not in seen:
            seen.add(value)
            result.append(value)
    return result

listだけで存在確認するとデータ増加時に遅くなりやすいため、確認用のsetと順序保持用のlistを組み合わせています。

理解チェック

データ構造を用途から選べる
O(n)とO(log n)の増え方を説明できる
二分探索にソート済みデータが必要な理由を説明できる
境界値を使ってアルゴリズムを検証できる

次に読む

テストとデバッグで、正しさを継続的に確かめる方法を学びます。