アルゴリズム的思考 — ソート・探索・計算量の直感

ソートと探索の具体的な手順をたどり、計算量の直感をつかみ、日常の問題をアルゴリズム化してみる。

この単元の目標

線形探索と二分探索の手順を説明し、比較回数の違いを数値で見積もることができる
バブルソートと選択ソート、マージソートの動きと計算量の違いを説明できる
身近な問題を「入力・手順・出力」に分解し、計算量の観点から改善点を見つけられる

📑 目次

アルゴリズムとは — 手順の良さを比べる
探索 — 線形探索と二分探索
ソート — 三つの代表選手
日常問題をアルゴリズム化する
練習問題
確認クイズ

アルゴリズムとは — 手順の良さを比べる

アルゴリズムとは、問題を解くための明確で有限な手順のことです。同じ問題でも手順によってかかる時間が桁違いに変わります。辞書で単語を探すとき、最初のページから順にめくる人はいません。まず中央付近を開いて前半か後半かを絞りますよね。この「半分に絞る」発想こそ、効率的な探索の出発点です。コンピュータの場合、手順の良さをステップ数（基本操作の実行回数）で測ります。入力サイズ $n$ が大きくなったとき、ステップ数がどの程度増えるかを見積もる感覚を、ここでは「計算量の直感」と呼びます。

探索 — 線形探索と二分探索

線形探索: 先頭から順に1件ずつ調べる。並び順は不要。最大 $n$ 回の比較
二分探索: 整列済み配列の中央を調べ、比較済みの中央を除いて範囲を絞る。大小・一致の判定をまとめて1回と数えると、最大 $\lfloor \log_2 n \rfloor + 1$ 回（ $n \ge 1$ ）

100万件のデータを探す場面で比べましょう。線形探索は最悪 100万回。二分探索は $\log_2 1{,}000{,}000 \approx 20$ 回です。20回と100万回——これが「ソート済み」という前提が買ってくれる速度です。もちろん二分探索には事前に整列が必要なので、検索を1回しかしないなら線形探索のほうが速いこともあります。アルゴリズムの選択は、データの状態と使用回数次第というのが実践的な考え方です。

例題

昇順に並んだ 8 個のカード [3, 7, 11, 15, 19, 23, 29, 31] から 23 を二分探索で見つける手順を示せ。

解答・解説

中央は偶数個なら左寄りを選びます。① 左から4番目の15と比較 → [19, 23, 29, 31]。② この4個の左から2番目の23と比較 → 発見。**2回**です。線形探索では先頭から6回かかります。

ソート — 三つの代表選手

アルゴリズム	手順のイメージ	計算量の目安	特徴
バブルソート	隣同士を比較・交換を端から繰り返す	$O(n^2)$	遅いが理解しやすい。安定な整列
選択ソート	最小値を探して先頭に置き、範囲を狭める	$O(n^2)$	交換回数が少ない。不安定な場合がある
マージソート	分割して整列し、統合（マージ）する	$O(n \log n)$	速い。作業用メモリが必要。安定な整列

最悪時の処理量を $n^2$ に比例すると近似すれば、データ量が2倍になると約4倍です。 $n \log_2 n$ 型の増加率は元の件数にも依存します。例えば1000件から100万件なら、比は $1000 \times (\log_2 10^6 / \log_2 10^3) = 2000$ 。同じ条件で $n^2$ 型は100万倍です。これは増え方の比較で、実測時間そのものを保証する値ではありません。

$O(1)$ : 配列の i 番目を参照する —— データ量によらず即座に終わる
$O(\log n)$ : 二分探索 —— 100万件でも約20回
$O(n)$ : 全件チェック —— 件数に比例
$O(n \log n)$ : マージソートなど高速な整列
$O(n^2)$ : 二重ループ —— 全ペア比較。1000件なら約100万回

ビッグオーは、十分大きな入力に対する増え方の上限を、定数倍を無視して表す記法です。例えば

3n + 2

は

O(n)

です。厳密には

O(n^2)

とも書けるので、比較ではできるだけきつい上限を用います。実行時間は実装や機器にも依存します。

日常問題をアルゴリズム化する

アルゴリズム的思考は、問題を入力・出力・手順に分解し、手順の重複や無駄を疑うことです。例：「クラス30人の好きなたこ焼きの具を集計する」。手順A＝各人の回答を聞くたび、紙のリストを上から走査して該当欄に印を付ける。手順B＝具の種類ごとに列を用意し、回答ごとに対応する列へ直接印を付ける。手順Bは「検索を繰り返す」構造を「索引を引く」構造に変えたもので、計算量でいうと $O(n \times k)$ （ $k$ は具の種類数の走査）から $O(n)$ へ改善しています。

例題

「学校祭で売れた商品を金額順に並べて上位5品を発表する」作業をアルゴリズム化し、改善のポイントを1つ挙げよ。

解答・解説

① 各商品の売上金額を入力する（ $O(n)$ ）② 金額順に整列する（マージソートなら $O(n \log n)$ ）③ 先頭5件を出力する（ $O(1)$ ）。改善点：上位5件だけ欲しいなら全体を整列しなくても、「現在のトップ5」を保持しながら1件ずつ読む方法で $O(n \times 5) = O(n)$ にできる（部分選択の考え方）。

練習問題

整列済み配列16個を二分探索する。中央要素との大小・一致の判定をまとめて1回と数えると、最悪で何回か。
ヒント
候補が1個になった後にも、その要素との比較が必要です。
解答・解説
**5回**。 $\lfloor \log_2 16 \rfloor + 1 = 5$ 。左寄りの中央を選んで最大要素を探すと、候補数は16 → 8 → 4 → 2 → 1と減り、最後の1個とも比較します。
通常のバブルソートで1000件を整列するとき、各周で比較範囲を1個ずつ減らし、途中終了しない場合の比較回数を求めよ。
ヒント
999 + 998 + … + 1 を計算します。
解答・解説
$999 + 998 + \cdots + 1 = 1000 \times 999 / 2 = 499500$ 回です。 $O(n^2)$ は増え方であって、比較回数がちょうど $n^2$ という意味ではありません。
「図書室で借りたい本の請求番号を探す」作業に二分探索を適用するために必要な前提条件を答えよ。
ヒント
二分探索が機能するためのデータの整え方。
解答・解説
対象の本のリスト（または棚）が**請求番号順に整列されている**こと。未整列なら先に整列が必要で、1回きりの検索なら線形探索の方が合理的な場合もある。
「毎朝の登校準備」をアルゴリズム化するとき、計算量の観点からの改善例を1つ挙げよ。
ヒント
同じ場所を何度も探している手順はないか。
解答・解説
必要な道具を決まった場所に置き、毎回すべての候補を探す手間を減らします。ただし必要物 $n$ 個を確認して詰める作業は依然 $O(n)$ です。前日に移すだけで全体が $O(1)$ になるわけではありません。

確認クイズ

問1. 二分探索を使うために必要な前提条件はどれか。

問2. データ件数が 2 倍になったとき、処理時間がおよそ 4 倍になる計算量はどれか。

問3. 100 万件の整列済みデータを二分探索するときの最悪比較回数に最も近いのはどれか。

📝 メモこの端末のみに保存

メモ欄はページ読み込み後に使えるようになります。