探索アルゴリズムの時間計算量の基礎

「同じ“探す”でも、やり方次第でスピードが何倍も変わるって本当？」——そんな疑問を持ったことはありませんか。Pythonでデータを探すとき、どのアルゴリズムを選ぶかで処理時間は大きく変わります。

今回は、IT初心者にもわかりやすい形で時間計算量（ビッグオー記法)の直感をつかみつつ、線形探索と二分探索の違いを丁寧に解説します。コードの動きも、読み物のように追えるよう説明していきます。

時間計算量ってなに？（やさしい直感）

まずはウォームアップです。時間計算量とは、「入力の大きさが大きくなるとき、処理時間がおおまかにどう増えるか」を表す指標です。詳しい数式を知らなくても、増え方の傾向だけ押さえれば十分に使えます。「ビッグオー記法」と呼ばれ、O(1)、O(n)、O(log n) のように書きます。ここで n は「データ件数（要素数）」のことです。

いくつか代表的な増え方を目でイメージしておきましょう。以下はよく登場する順番の参考です（左が速い傾向）。

まずは増えにくいもの: O(1)（一定時間）、O(log n)（半分ずつ狭める）
次に増えやすいもの: O(n)（要素数に比例）
さらに重くなりやすいもの: O(n log n)、O(n^2) など（ソートや二重ループで出てきがち）

厳密な秒数ではなく「増え方の違い」をつかむのがポイントです。では実際の探索アルゴリズムを見ていきましょう。

1. 線形探索の計算量: O(n)

まずは一番シンプルな「片っ端から見る」方法です。リストの先頭から順に、探したい値と一致するかを1つずつ確かめていきます。見つかったらそこで終了、見つからなければ最後まで調べます。日常で言えば、引き出しの中身を上から順に確認していくイメージですね。「少ないデータならこれで十分」という場面も多いです。

線形探索の例（Python）

# 配列内でターゲット値を探す
arr = [1, 3, 5, 7, 9]
target = 9

for i in range(len(arr)):
    if arr[i] == target:
        print(f"Found at index {i}")
        break

このコードはとても素直です。先頭から i を増やしながら、arr[i] が target と一致した瞬間に見つかった位置を表示してループを抜けます。ターゲットが末尾にある場合や存在しない場合は、最後まで順に確かめることになるため、必要な比較回数は要素数 n にほぼ比例します。これが時間計算量 O(n) という意味です。運が良ければ最初の1回で見つかることもあるので、最良ケースは O(1)、平均や最悪では O(n) という見方をします。

なお、Python のリストに対する in 演算子（target in arr）や list.index は、基本的にこの線形探索と同じ増え方（O(n)）になります。「とりあえず動かす」「データが小さい」ときは気軽に使えますが、データが増えると遅くなりやすい点は覚えておきましょう。

2. 二分探索の計算量: O(log n)

次に、「範囲を半分に狭めながら探す」方法です。条件はひとつ。データがあらかじめ昇順（または降順）にソートされていること。ソート済みなら、真ん中を見るだけで「左側にあるか」「右側にあるか」を判断でき、無駄な確認を大幅に減らせます。まるで本の索引で、だいたいのページを一気に絞り込むような感覚です。

二分探索の例（Python）

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2  # 中央のインデックス
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1      # 右半分に絞る
        else:
            right = mid - 1     # 左半分に絞る
    return -1

arr = [1, 3, 5, 7, 9]
target = 9
print(binary_search(arr, target))  # 出力は 4（インデックス）

この関数は、left と right で探索範囲を表し、中央 mid の要素を調べて「左に寄せるか」「右に寄せるか」を決めています。1回の比較で探索範囲がほぼ半分になるため、必要な比較回数はデータ数 n に対して対数的に増えます。これが O(log n) です。つまり、n が何倍になっても、比較回数は少しずつしか増えません。最良ケースは1回で見つかるので O(1)、平均や最悪でも O(log n) という捉え方をします。

注意点として、二分探索は「ソートされていること」が前提です。毎回ソートから始めると O(n log n) のコストが別途かかるため、単発で1回だけ探すなら線形探索のほうが速いこともあります。逆に「同じ配列に対して何度も検索する」なら、最初に一度ソートしておき、二分探索（または bisect モジュール）で繰り返し高速に探すのが定石です。

また、Python には bisect モジュールがあり、二分探索での挿入位置や検索に便利です。実装バグ（オフバイワンなど）の心配を減らせるので、初心者にもおすすめです。

計算量の違いはどれくらい効くの？

ここでは、増え方の違いを体感しやすいように、規模の違うデータを想像してみましょう。数字はあくまで比較の目安です。

小さなデータ（例えば n = 100）：線形探索でも一瞬です。実装がシンプルなほうを選んでも問題になりにくいでしょう。
中くらいのデータ（n = 10,000～100,000）：線形探索は目に見えて遅くなり始めます。二分探索の恩恵が出てきます。
大きなデータ（n = 1,000,000）：線形探索は最悪100万回比較、二分探索は20回前後の比較で済みます。差は歴然です。

「え、本当にそんなに違うの？」と思った方は、次の簡単な計測コードで実感してみましょう。

計ってみる

このサンプルは、リストの作成と探索の時間をざっくり比べるためのものです。まずは小さめの n から試し、あとで n を大きくして違いを観察すると良いでしょう。

import time
import bisect
import random

# データ準備
n = 1_000_00  # 10万件（値は調整してOK）
arr = list(range(n))  # ソート済み
targets = [random.randint(0, n - 1) for _ in range(1_000)]

# 線形探索の計測
start = time.time()
hits = 0
for t in targets:
    # in はリストでは O(n) 相当
    if t in arr:
        hits += 1
lin_time = time.time() - start

# 二分探索（bisect）の計測
start = time.time()
hits_b = 0
for t in targets:
    idx = bisect.bisect_left(arr, t)
    if idx < len(arr) and arr[idx] == t:
        hits_b += 1
bin_time = time.time() - start

print(f"linear hits={hits}, time={lin_time:.4f}s")
print(f"binary hits={hits_b}, time={bin_time:.4f}s")

ここでは、線形探索として in を使い、二分探索として bisect_left を使っています。どちらも見つけた件数は同じになるはずですが、n を増やしていくと処理時間の差が広がるのが分かるでしょう。「小さいうちは誤差、大きくなると本質的な差」——これが時間計算量の考え方です。

まとめ

最後に要点を整理して、今日の学びを自分の言葉に落とし込んでみましょう。どの場面で何を選ぶか、もう迷わなくなるはずです。

線形探索はシンプルで扱いやすく、時間計算量は O(n)。小規模データや単発の検索に向いています。
二分探索はソート済みが前提で、時間計算量は O(log n)。大規模データや繰り返し検索に強いです。
迷ったら、「データはソート済み？」「検索は何回？」「規模はどれくらい？」の3点をチェック。
Python なら、手軽な in（O(n)）と、堅実な bisect（ほぼ O(log n)）を使い分けるのがおすすめ。

次のステップでは、実際に自分のデータで計測してみてください。「本当に速いのはどっち？」という問いに、あなた自身の手で答えを出せるようになります。どのアルゴリズムを選ぶか——それが“Pythonで考える力”の第一歩です。

前に戻る一覧に戻る

メニュー

User

Python WebAcademy