計算量と小さい反例｜論理・アルゴリズム・情報の基礎

このページはプロモーション（広告）を含みます。

論理・アルゴリズム・情報の基礎（中級・読む25分＋演習35分）

この授業のゴール

• 「全件を見る」手順の操作回数が、件数の増加に対してどう増えるか（n、n²、log n）を数値で比較できる
• 実行時間の体感ではなく、操作回数を数えて手順の費用を見積もれる
• 小さい入力（0件・1件・同値・境界）で誤りを見つけ、反例を1つ示して手順が誤りだと説明できる
• 全件走査と境界値の検査の費用を比べ、検査ケースの選び方を説明できる

仕事でどう使うか

データの仕事では、「手元の100件では一瞬で終わったのに、本番の1億件では終わらない」という事態が起こります。また、数個の例で動いたからと安心した手順が、特別な入力（空、同点、境界）で誤った結果を返すこともあります。手順の費用の増え方と、小さい反例で誤りを見つける方法は、どの職種でも使う基本の判断力です。

この授業のゴールは、「全件走査の費用」と「少数の境界ケースで十分な検査」を、数値で使い分けられるようになることです。

前提

次の言葉と操作を使います。不安があれば先に戻ってください。

• 手順・分岐・繰り返しと追跡表 → 手順・分岐・繰り返し
• 条件、必要条件・十分条件、反例 → 真偽とAND・OR・NOT、条件と必要十分条件
• 入力・出力・状態 → 入力・出力・状態
• 累乗と指数（$2^{10}=1024$）→ 四則計算と計算順序
• Python の for、リスト、set（重複を持たない集まり）は、使いながら説明します → 「forとrange」（有料版）

コードは、画面内の 実行 ボタンで動かせます。実行前に、数字を予想してください。

身近な状況：5万件の注文に、同じ注文IDが2つある？

注文データの取り込みで、同じ注文IDが2回入っていないかを確認することになりました。件数は5万件です。担当者の最初の案は、次のとおりです。

1件目を、2件目以降の全部と比べる。2件目を、3件目以降の全部と比べる。…これを最後まで続ける。

この手順は正しいのですが、何回比べるかを数えてみましょう。n件のとき、比べるペアの数は $\frac{n(n-1)}{2}$ です。小さい件数で、実際に数えます。

def has_duplicate_slow(values):
    comparisons = 0
    n = len(values)
    for i in range(n):
        for j in range(i + 1, n):
            comparisons += 1
            if values[i] == values[j]:
                return True, comparisons
    return False, comparisons

for n in [10, 100, 1000]:
    print(n, '件（重複なし）の比較回数:', has_duplicate_slow(list(range(n)))[1])

出力は、10件で45回、100件で4,950回、1,000件で499,500回です。件数が10倍になると、比較回数は約100倍になっています。5万件なら、約12.5億回です。一方、1件ずつ「見たことのあるIDか」を記録して調べる方法なら、約5万回で済みます。

「正しい手順」と「使える手順」は別です。この授業では、手順の費用を数える方法と、少ない例で誤りを見つける方法を学びます。

直感的な説明：名簿の探し方と、「費用の増え方」

1,000人の名簿から、ある人を探す3つの方法を考えます。

1. 端から順に見る：最悪、1,000人全員を見ます（全件走査）。
2. 五十音順に並んだ名簿を、真ん中から開いて半分に絞る：1回見るごとに候補が半分になります。1,000人なら10回ほどで見つかります。
3. 索引（目次）を使う：目的のページに直接飛びます。見る回数は、人数にほとんど依存しません。

件数が増えたとき、1.は件数に比例して増え、2.はゆっくりとしか増えません。この「件数が増えたときに、操作の回数がどう増えるか」が、手順の費用の考え方です。

もう1つの比喩として、検査員が100個の製品を、1個ずつ全部検査するのと、規格の境界（重さの下限・上限）の製品だけを検査するのを比べましょう。境界の製品は、合格と不合格が切り替わる場所なので、少ない数でも誤りを見つけやすいのです。ただし、これは「条件が境界で切り替わる」構造がわかっているときだけ通用する考え方です。

たとえ話の限界：名簿の比喩では、並べ替える手間や索引を作る手間は考えていません。実際の手順では、準備の費用（並べ替え、索引の作成）と使うときの費用の両方を評価します。

正確な定義：計算量・全件走査・小さい反例

計算量とは、入力の大きさ $n$（件数など）に対して、手順が行う基本操作の回数が、どのように増えるかを表したものです。実行時間（秒）そのものではなく、機械の速さに依存しない操作の数え方を使います。

主な増え方は次のとおりです。$O(\cdot)$ は「$n$ が大きいとき、およそこの形で増える」ことを表す記法で、「オーダー」と読みます。

ここで $\log n$ は、2を何回かければ $n$ に届くかを表します（底は2）。$n=1{,}000$ なら $2^{10}=1{,}024$ なので約10です。$O(n^2)$ の列は $\frac{n(n-1)}{2}$ を代入した値です。$n=100{,}000$ のとき $\frac{100000\times 99999}{2}=4{,}999{,}950{,}000$ で、約50億になります。

全件走査とは、データの全件を1回ずつ見る手順です。$O(n)$ であり、件数が2倍なら費用も2倍です。

次のコードで、全件走査（線形探索）と、並んだデータを半分ずつ絞る手順（二分探索）の、探す回数を比べます。linear_search と binary_search は、リストと探す値を受け取り、(位置, 見た回数) の組を返します。

def linear_search(sorted_list, target):
    steps = 0
    for i, v in enumerate(sorted_list):
        steps += 1
        if v == target:
            return i, steps
    return -1, steps

def binary_search(sorted_list, target):
    lo, hi = 0, len(sorted_list) - 1
    steps = 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if sorted_list[mid] == target:
            return mid, steps
        elif sorted_list[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, steps

data = list(range(0, 200000, 2))      # 100,000件の昇順の偶数
print('全件走査:', linear_search(data, 199998))
print('二分探索:', binary_search(data, 199998))

10万件のうち最後の要素を探すと、全件走査は100,000回、二分探索は17回です。ただし、二分探索はデータが並んでいることが前提です。並んでいないデータには使えません。

小さい反例とは、手順が誤りであることを示す、小さな入力例のことです。「正しいこと」の証明には全部の入力が要りますが、「誤りであること」の証明は、1つの反例で足ります。反例を探すときは、まず小さい入力（0件、1件、2件）、同じ値の重複、境界の値、負の数から試します。小さい入力のほうが、結果を手で追えるので、原因を特定しやすいからです。

段階付き例題：重複検出を速くし、操作回数で確かめる

問題：5万件の注文IDに重複があるかを、総当たり（約12.5億回）より少ない操作で調べてください。

ステップ1：考え方を決める。「すでに見たIDの集まり」を持ち、新しいIDが出るたびに、その集まりにあるかを調べます。集まりには、set（セット：重複を持たず、「あるか」を速く調べられる集まり）を使います。set の「あるか」の調べは、件数にほとんど依存しません（平均的に $O(1)$）。

ステップ2：コードにする。入力は値のリスト、出力は (重複があるか, 調べた回数) の組です。

def has_duplicate_fast(values):
    seen = set()
    lookups = 0
    for v in values:
        lookups += 1
        if v in seen:
            return True, lookups
        seen.add(v)
    return False, lookups

for n in [10, 100, 1000, 50000]:
    print(n, '件（重複なし）の調べた回数:', has_duplicate_fast(list(range(n)))[1])
print(has_duplicate_fast([5, 3, 5, 9]))
print(has_duplicate_fast([]))

ステップ3：結果を読む。重複がなければ、調べた回数は件数と同じです（10件なら10回、5万件なら5万回）。総当たりの約12.5億回と比べて、約2万5千分の1です。重複があるときは、最初の重複を見つけた時点で止まります（[5, 3, 5, 9] は3回で終了）。

ステップ4：正しさを小さい反例で検査する。速くしても、正しくなければ意味がありません。小さい入力で確かめます。

ステップ5：意味を言葉に戻す。「5万件の重複確認は、見たIDを記録する方法で約5万回の操作で済む。ただし、記録するためのメモリが件数に比例して必要になる」。速さと引き換えに、メモリを使っています。費用は、時間だけでなく、メモリや準備の手間も含めて考えます。

操作して理解する：割引関数の誤りを、小さい反例で見つける

会員割引の仕様（会員かつ3,000円以上は10%引き、円未満切り捨て）を実装した関数があります。担当者が >=（以上）を >（超える）と書き間違えた関数 buggy_gt を、仕様どおりの関数 spec と比べます。実行する前に、反例（結果が違う入力）は何件あるか、予想してください。

def spec(member, amount):
    # 仕様：会員かつ3000円以上は10%引き（円未満切り捨て）
    return amount * 90 // 100 if (member and amount >= 3000) else amount

def buggy_gt(member, amount):
    return amount * 90 // 100 if (member and amount > 3000) else amount

# 全件走査：会員の真偽(2通り) × 0〜5000円(5001通り)
diffs = [(m, a) for m in (False, True) for a in range(0, 5001)
         if spec(m, a) != buggy_gt(m, a)]
print('調べた組み合わせ:', 2 * 5001)
print('反例の数:', len(diffs), diffs)

# 境界の値だけを調べる：2通り × 3つの金額
cases = [(m, a) for m in (False, True) for a in (2999, 3000, 3001)]
found = [(m, a) for m, a in cases if spec(m, a) != buggy_gt(m, a)]
print('調べた組み合わせ:', len(cases), ' 見つかった反例:', found)

予想と答え：

• 反例は (会員, 3,000円) の1件だけです。3,000円ちょうどで、仕様は2,700円、誤った関数は3,000円を返します。
• 全件走査では10,002通りを調べて、1件の反例が見つかります。境界の値だけなら6通りで、同じ反例が見つかります。

次に、自分で書き換えてみましょう。

1. buggy_gt を、会員の条件を or（または）に変えた関数にすると、反例は何件になりますか（調べる範囲は同じ）。反例のうち、最も小さい金額と、その会員区分は何ですか。
2. 境界の6通りだけを調べる方法で、(1) の誤りを見つけられますか。

答えは、(1) 反例は大量にあります。非会員の3,000円以上（3,000〜5,000円の2,001件）と、会員の1〜2,999円（2,999件）で、合計5,000件です。会員の0円は、割引しても0円で同じため、反例になりません。反例のうち金額が最も小さいのは、(会員, 1円) です。(2) 6通りには、(会員, 2,999円)、(非会員, 3,000円)、(非会員, 3,001円) が含まれるので、見つけられます。

注意：境界の値だけの検査が有効なのは、条件が不等式の境界で結果が切り替わる構造のときです。複雑な計算や、たくさんの条件が絡む場合は、ランダムな入力や全件の比較も併用します。

発展：最悪の場合・平均・準備の費用と、検査の網羅

最悪の場合と平均：計算量は、通常最悪の場合で評価します。全件走査は、探す値が先頭にあれば1回で終わりますが、最後にある場合や、存在しない場合は $n$ 回かかります。実務では平均的な場合も重要ですが、最悪の場合を知っておくと、締め切りやシステムの設計を守れます。

準備の費用：二分探索には、データが並んでいる必要があります。並べ替えには、一般に $O(n \log n)$ の操作が要ります。データを1回しか探さないなら、並べ替えて二分探索するより、全件走査のほうが安いことがあります。何回探すかによって、有利な手順が変わります。

メモリと時間のトレードオフ：set を使う重複検出は、時間を節約するかわりに、見たIDを保存するメモリを使います。データが非常に大きければ、メモリが不足することもあります。時間・メモリ・実装の手間のどれを優先するかは、目的で決まります。

検査の網羅：条件が $k$ 個あれば、真偽の組み合わせは $2^k$ 通りで、全部を調べる費用は急増します（真偽とAND・OR・NOT）。10個の条件なら1,024通りです。実務では、(1) 条件が切り替わる境界、(2) 空・1件・重複・負の数のような端の入力、(3) 過去に不具合を起こした入力、の順で検査ケースを選びます。

反例と証明：反例が見つからないことは、手順が正しいことの証明ではありません。重要な手順では、数学的な性質（たとえば「並べ替えた結果は、元の要素と同じ要素を持つ」）を明示して、ランダムな入力で大量に検査する方法もあります。この方法は、後の学習で出てくるテストの考え方につながります（「仕様と簡単なテスト」（有料版））。

よくある失敗

失敗1：小さい入力の「一瞬だった」で、本番の費用を判断する

10件で一瞬だったので、1億件でも問題ないと判断してしまう誤りです。時間を測る代わりに、操作回数の式で見積もります。

for n in [10, 1000, 100000]:
    pairs = n * (n - 1) // 2
    print(f'{n:>7,} 件  全件走査 {n:>9,} 回   総当たり {pairs:>14,} 回')

10件では45回ですが、10万件では約50億回です。全件走査なら10万回で済みます。件数が10,000倍になると、総当たりは約1億倍（$10^4$ の2乗）になります。

直し方：手順の中のループが何重になっているかを数える。1重なら件数に比例、2重（全ペア）なら件数の2乗に比例します。件数が増える場合は、本番に近い大きさで検査するか、操作回数の式で見積もります。

失敗2：2〜3個の例が通っただけで、「正しい」と判断する

最大値を返す関数を、最初の値を0にして書いた例です。

def buggy_max(values):
    best = 0                     # 最初の値を0にしたのが誤り
    for v in values:
        if v > best:
            best = v
    return best

def right_max(values):
    best = values[0]
    for v in values:
        if v > best:
            best = v
    return best

print(buggy_max([3, 1, 2]), right_max([3, 1, 2]))
print(buggy_max([10, 20]), right_max([10, 20]))
print(buggy_max([-5, -2]), right_max([-5, -2]))
print(buggy_max([0]), right_max([0]))

正の数だけの例（[3, 1, 2]、[10, 20]）では、どちらも同じ結果で、誤りに気づけません。[-5, -2] で初めて、誤った関数が0を返し（正しくは−2）、誤りがわかります。この1件が反例です。なお、right_max は空のリストを渡すとエラーになるため、仕様（空のときの扱い）を決めておく必要があります。

直し方：検査ケースに、負の数、1件、同じ値、空、境界の値を必ず入れる。通った例の数ではなく、反例を探して見つからなかった範囲を報告します。

失敗3：ループの中で、気づかずに全件走査を繰り返す

重複を取り除く手順で、「見たIDの集まり」をリストにすると、seen の中を毎回端から探すことになります。操作回数を数えて確かめます。

def dedupe_list(ids):
    seen = []
    comparisons = 0
    for x in ids:
        found = False
        for s in seen:                # seen を端から全部見る
            comparisons += 1
            if s == x:
                found = True
                break
        if not found:
            seen.append(x)
    return seen, comparisons

def dedupe_set(ids):
    seen = set()
    out = []
    for x in ids:
        if x not in seen:
            seen.add(x)
            out.append(x)
    return out, len(ids)

ids = list(range(1000))
print('リスト版の比較回数:', dedupe_list(ids)[1])
print('set版の調べた回数  :', dedupe_set(ids)[1])

リスト版は499,500回、set 版は1,000回です。Python の x in リスト という書き方も、内部では端から順に全件を比べています。1行で書けるので気づきにくいのですが、ループの中に全件走査が隠れていると、全体が件数の2乗になります。

直し方：ループの中で、リストに対する in や検索を使っていないか確認する。何度も「あるか」を調べるなら、set や辞書に変える。メモリを多く使うことは、トレードオフとして記録します。

まとめ

• 計算量は、件数 n に対する操作回数の増え方。全件走査は n に比例し、全ペアの総当たりは $n^2$ に比例して、件数が10倍で約100倍になる。
• 実行時間の体感ではなく、操作回数を数えて見積もる。ループの中に全件走査（リストへの in など）が隠れていないか点検する。
• 手順の誤りは、反例1件で示せる。空・1件・同じ値・負の数・境界の値のような小さい入力から試す。
• 条件の検査では、境界とその前後が誤りを露呈しやすい。ただし、通ったことは正しさの証明ではなく、調べた範囲の話。

用語

計算量（computational complexity）

入力の大きさ n に対して、手順の基本操作の回数（時間計算量）やメモリ使用量がどう増えるかを表したもの。

全件走査（full scan）

データの全件を1回ずつ見る手順。計算量はO(n)。

二分探索（binary search）

並んだデータの中央と比べて、探す範囲を半分に絞る手順。計算量はO(log n)。データが並んでいることが前提。

反例（counterexample）

手順や主張が誤りであることを示す、1つの入力例。小さい入力ほど原因を追いやすい。

境界値（boundary value）

条件の結果が切り替わる値と、その前後の値。3,000円以上なら2,999・3,000・3,001円。

よくある質問

なぜ、実行時間ではなく操作回数で考えるのですか？

実行時間は、機械の性能、他のプログラム、データの置き場所で変わります。操作回数の増え方なら、機械が変わっても通用し、件数が10倍・100倍になったときの見通しが立てられます。ただし、最終的には、本番に近いデータで実測して確かめます。

$O(n \log n)$ や $O(2^n)$ は、どんな手順ですか？

$O(n \log n)$ は、並べ替えに多い増え方で、$n^2$ よりずっと緩やかです。$O(2^n)$ は、全部の部分集合を試すような手順で、$n=30$ で約10億通り、$n=50$ で約1,100兆通りになり、実用になりません。「全パターンを試す」設計の限界の目安です。

計算量が小さいほうが、常に良い手順ですか？

いいえ。件数が少なければ差は無視でき、分かりやすい実装のほうが良いことがあります。また、計算量の小さい手順は、並べ替えや索引など準備が必要で、メモリも使います。件数、検索の回数、メモリの余裕から判断します。

反例を探すとき、どんな入力から試せばよいですか？

空、1件、同じ値、境界の値、負の数、最大・最小の値の順に試します。さらに、過去の不具合の入力を加えます。小さい入力なら結果を手で追えるので、どの行で想定とずれたかを特定できます。

全件を調べずに「正しい」と言ってよいのですか？

全件を調べない限り、「正しいことの証明」にはなりません。言えるのは「調べた範囲で反例は見つからなかった」までです。重要度が高い手順は、数学的な説明（なぜ正しいか）と、検査の組み合わせで確からしさを高めます。

データ分析の仕事で、計算量を意識する場面は、どこですか？

データの結合、重複の検出、類似度の総当たり計算、ループの中の検索で、件数が増えたときに遅くなります。「ループの中に、全件を見る処理がないか」を点検するだけで、多くの遅い処理を避けられます。SQLでは、結合に使う列の索引でも、同じ考え方が使われます。

確認問題

次に学ぶこと

これでON06の6授業が終わりです。モジュールの総合テストと、会員割引の条件分岐を表で検証し、境界ケースを作る自力課題に進んでください。

並べ替えと探索のアルゴリズムは、後続のPythonやデータ構造の学習で扱います。境界ケースの検証は 「境界ケースの検証」（有料版）、関数の仕様と簡単なテストは 「仕様と簡単なテスト」（有料版）、SQLでの走査と結合の費用の感覚は 「走査と結合の費用」（有料版） で続きます。この授業の確認問題だけでモジュールの習得とはしません。