計算量の考え方｜情報Ⅰ 最強120講義 第57講

こんにちは、数強塾代表の藤原進之介です。この記事は参考書『藤原進之介の最強120講義』の第57講「計算量の考え方」のWeb版です。共通テスト「情報Ⅰ」での重要度はB（出題実績あり。取り切りたい）、情報Ⅱでの接続先は(4)情報システムとプログラミングです。

第55講（線形探索と二分探索）で比較回数を数え、整列でも回数を数えました。この講はその先です。個別のアルゴリズムの手順ではなく、「入力が増えたとき、伸び方がどう違うか」だけを扱います。 ここを一度きちんと通しておくと、共通テストの「改良して処理回数を減らす」タイプの設問が、暗記ではなく判断で解けるようになります。

1. この講の問い

なぜアルゴリズムの良し悪しを「何秒かかったか」ではなく、「回数の伸び方」で測るのか。

2. 結論

3. なぜそうなるのか

3-1. なぜ「秒」で測ってはいけないのか

同じアルゴリズムでも、実行時間は次の3つで簡単に何倍も変わります。

• 機械（CPU・メモリ・その日の負荷）
• 言語と処理系（同じ手順を Python で書くか C で書くか）
• 入力そのもの（同じ n でも、探す値が先頭にあるか末尾にあるか）

だから「私のパソコンでは0.8秒でした」は、他人にとって何の情報でもありません。国の教材も、3つ目をはっきり書いています。情報Ⅰ教員研修用教材 第3章 学習15「アルゴリズムの比較」の【研修の目的】です。

アルゴリズム・データ数・探索する値。 変数が3つある以上、1つの秒数では何も言えません。

ところが、この3つのうち機械と言語は「全体を何倍かする」働きしかしません。速い機械なら全部が一律に速くなる。つまり機械と言語は定数倍であって、n が増えたときの「増え方の形」を変えないのです。残るのは n との関係だけ。だから計算量は、時間ではなく「n の関数としての操作回数」で測ります。

3-2. なぜ定数倍と低次の項を捨てるのか

「n²+100n」と「n²」は、式としては別物です。それでも捨ててよいのは、n が大きくなると差が消えるからです。

n=10 では 100n のほうが n² の10倍も大きい。ところが n=1,000,000 では 0.01% にしかなりません。n が小さいうちは低次の項が主役で、n が大きくなると最高次の項が主役になる。 計算量は「n が大きくなったとき」の話ですから、後者だけを見ればよいのです。

これは机上の理屈ではありません。全部の2つ組を調べるアルゴリズム（比較回数は n(n−1)/2、つまり 0.5n² − 0.5n）で、n を10倍にしたときの実測倍率を見てください。

110.00 → 100.91 → 100.09。 低次の項（−0.5n）が消えていく様子が、そのまま数字に出ています。定数倍（0.5）に至っては、倍率を取った時点で最初から消えます。だから最後に残るのは「n²」という形だけになるのです。

3-3. n を10倍にしたら何倍になるか

計算量の実感は、この一問に集約されます。n を10倍にしたとき、仕事量は何倍になるか。

log n だけが「倍率」ではなく「差」で効く。ここが決定的な違いです。n が 1,000 → 10,000 になっても、log₂n は 9.97 → 13.29 と 3.32 増えるだけ。データが10倍になっても仕事は3つ半しか増えません。二分探索が強いのはこれです。

3-4. 2ⁿ は「速い機械を買う」では絶対に解決しない

n=100 の全組合せを調べる、というだけの話を考えます。

2¹⁰⁰ = 1,267,650,600,228,229,401,496,703,205,376（31桁）

1秒間に1兆回（10¹²回）調べられる機械を用意しても、1.2677×10¹⁸秒。1年を365.25日として約401.7億年かかります。

ここで大事なのは「長い」ことではありません。機械を1000倍速くしても、n が10増えれば元に戻ることです。2ⁿ は n が1増えるたびに2倍になりますから、1000倍の性能向上は 2¹⁰ = 1024 ≒ 「n を10だけ延ばす力」しかない。指数関数の前では、ハードウェアの進歩は「ほんの少し先へ進む」以上の意味を持ちません。 これが「計算量」という考え方が存在する最大の理由です。

そしてこの話は、高校の一次資料の中にもう書かれています。文科省「情報Ⅱ」教員研修用教材 第3章後半、アソシエーション分析（買い物かごの分析）の節です。

「全ての組み合わせ」が 2ⁿ、「現実的な時間で収まらない」が上の401.7億年です。国の教材が、レシートの分析という身近な題材で組合せ爆発を書いている。この一節は、高校の一次資料で「計算量」という語が概念として説明される、ほとんど唯一の場所でもあります（この点は3-7で詳しく書きます）。

3-5. 計算量は1つの数ではない（最悪・平均・最良）

線形探索で、1,000件の配列の全要素を1回ずつ探してみると、比較回数はこうなります。

同じアルゴリズムで1回と1,000回です。 だから「線形探索は何回か」という問いは、最悪か平均かを言わなければ答えられません。入試でも実務でも、既定値は最悪です。理由は単純で、平均で設計すると「たまたま最悪のデータが来た日」にシステムが落ちるからです。

3-6. 時間だけがコストではない（空間とのトレードオフ）

「速くしたい」と思ったとき、いちばん確実な手はたいていあらかじめ表を作って引くことです。ですが表は場所を食います。

私の手元の Python 3 で、10万個の整数を保持するのに必要なサイズを測ると、リスト（順に並べるだけ）が 800,056バイト、集合（ハッシュ表。1回で見つかる）が 4,194,520バイト。約5.24倍でした。探すのが速くなる代わりに、メモリを5倍使うわけです。

この「時間と場所の取引」は、用語としてもきちんと存在します。IPA「応用情報技術者試験（レベル3）シラバス Ver.7.2」の基礎理論を見てください。

時間計算量と領域計算量。 この「領域計算量」が、いわゆる空間計算量です。計算量は最初から2軸なのです。

3-7. 大事な注意：O記法は高校の一次資料には無い

ここまで一度も O(n) と書かなかったのには理由があります。

「計算量」という語も「オーダ」という語も、高等学校学習指導要領解説 情報編の全文、情報Ⅰ教員研修用教材 第3章、情報Ⅱ教員研修用教材 第3章前半・第4章・第5章のいずれにも出てきません（私が2026年8月3日に全文検索して確認しました）。唯一の例外が、3-4で引いた情報Ⅱ教員研修用教材 第3章後半の2か所です。もう1か所は、ニューラルネットワークの歴史を説明する箇所です（後で引きます）。

つまり高校の一次資料では、効率は比較回数という具体的な数で語られ、記号は使われません。一方、資格試験の側では独立した項目になっています。並べると段差がはっきり見えます。

そしてもう一か所、意外な場所に「効率化」が明記されています。学習指導要領解説 情報編の専門教科の側です。第2章「専門教科情報科の各科目」第6節「情報システムのプログラミング」の〔指導項目〕(2)「データ構造とアルゴリズム」に、こうあります。

同じ節のデータ構造の項には「データ構造を適切に活用することで大量のデータを効率よく処理することができることを扱う」、データの型の項には「データの型の違いによる数値の精度やメモリへの影響，保存時のデータ容量や計算速度の違い」とあります。

同じ1冊の解説の中で、共通教科（情報Ⅰ・情報Ⅱ）には無い「アルゴリズムの効率化」「容量と計算速度」が、専門教科の側には書かれている。 つまり国は、計算量を「不要」と判断したのではなく、「共通必履修ではここまで踏み込まない」と線を引いたのです。

だから受験生の戦略はこうなります。記号は覚えなくてよい。伸び方の感覚だけを、数で持つ。

4. 手で確かめる

4-1. 5つの伸び方を n で並べる

2ⁿ の列だけ、n=100 の時点で数字として書けなくなります。これが「桁が壊れる」ということです。左端の log₂n の列は、n が10万倍になっても 3.32 から 19.93 にしかなりません。同じ表の中で、片方は6倍にしかならず、片方は書き切れなくなる。 これが計算量という考え方の全景です。

（2¹⁰⁰ は31桁、2¹⁰⁰⁰ は302桁、2の100万乗は301,030桁。すべて私が計算し、2通りの経路で照合しました。）

4-2. 操作回数を実際に数える

理論どおりに伸びるかは、自分の手で確かめられます。回数を数えるカウンタを入れただけの、ごく短いコードで十分です。

def linear(a, x):          # 先頭から順に見る
    c = 0
    for v in a:
        c += 1
        if v == x: return c
    return c
def binary(a, x):          # 半分ずつ捨てる
    lo, hi, c = 0, len(a) - 1, 0
    while lo <= hi:
        c += 1
        m = (lo + hi) // 2
        if a[m] == x: return c
        if a[m] < x: lo = m + 1
        else:        hi = m - 1
    return c
def allpairs(a):           # 全部の2つ組を調べる
    c = 0
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            c += 1
    return c
print(" n      線形   二分   全ペア")
prev = None
for n in (10, 100, 1000, 10000):
    a = list(range(n))
    lin = linear(a, -1)                      # 見つからない = 最悪
    bin_ = max(binary(a, v) for v in a)       # 全要素を探した最悪
    pai = allpairs(a)
    print("%6d %6d %6d %10d" % (n, lin, bin_, pai), end="")
    if prev:
        print("   -> 10倍で 線形x%.1f 二分+%d 全ペアx%.2f"
              % (lin / prev[0], bin_ - prev[1], pai / prev[2]))
    else:
        print()
    prev = (lin, bin_, pai)

実行結果です（2026年8月3日、私の手元の Python 3 で実行して確認しました）。

 n      線形   二分   全ペア
    10     10      4         45
   100    100      7       4950   -> 10倍で 線形x10.0 二分+3 全ペアx110.00
  1000   1000     10     499500   -> 10倍で 線形x10.0 二分+3 全ペアx100.91
 10000  10000     14   49995000   -> 10倍で 線形x10.0 二分+4 全ペアx100.09

読むべきは右端の1行です。

• 線形探索：きっちり10.0倍（n に比例）
• 二分探索：倍率ではなく +3 か +4（log に比例。log₂10＝3.32 なので3と4を行き来する）
• 全ペア：110.00 → 100.91 → 100.09 と100に収束（n² に比例し、低次の項が消えていく）

理論を先に信じる必要はありません。数えれば出てきます。 なお二分探索の最悪回数 4 / 7 / 10 / 14 は、floor(log₂n)+1 と完全に一致します（n=100,000 なら17、n=1,000,000 なら20）。

4-3. 空間とのトレードオフを測る

import sys
n = 100000
lst = list(range(n))
st  = set(lst)
print(sys.getsizeof(lst), sys.getsizeof(st), sys.getsizeof(st) / sys.getsizeof(lst))

出力は 800056 4194520 5.2427830051896365 でした。探索を速くする構造は、たいていメモリを余分に使う。 これが「表を作れば速いが場所を食う」の正体です。（処理系に依存する参考値です。数値そのものより「増える」という事実を見てください。）

5. 共通テストではこう出る（重要度 B）

O記法そのものが直接問われることは、まずありません。 高校の一次資料に無い記号を問うことはできないからです。出るのは、「データが増えたとき、どちらの方法が有利か」を判断させる形です。典型は次の3つ。

• プログラムの改良を問う設問。 素直に書いた処理と、無駄を省いた処理を比べ、後者の穴埋めや処理回数の比較をさせます。2026年度の第3問は「①手で考える → ②コードに落とす → ③処理回数を削減する改良」という3段構成だったと分析されています（大手予備校の分析。二次情報のため、設問構造の説明にとどめます）。
• 探索・整列の選択。 線形探索と二分探索、あるいは整列の方式を、条件つきで選ばせます。
• 前処理のコストを含めた判断。 情報Ⅰ教員研修用教材 学習15 は「最大探索回数だけを比較すると，回数の少ない二分探索がよいアルゴリズムと考えがちだが，二分探索には事前にデータを並べ替えておく必要があり，一概によいアルゴリズムとは言い切れない」と書いています。速い＝良い、ではありません。

引っかかりやすいのは次の3点です。

• 最悪と平均を取り違える。 線形探索 n=1,000 は最悪1,000回・平均500.5回。設問がどちらを聞いているかを必ず読むこと。
• n が小さい場合を忘れる。 定数倍と低次の項は、n が小さいうちはしっかり効きます。「データが少ないなら単純な方法が有利」というのは、教材が名指しで書いている判断です。
• 1回だけの処理に前処理をつけてしまう。 1回しか探さないなら、整列してから二分探索するより線形探索1回のほうが安く済みます。

プログラム問題そのものの読み方は第54講（プログラムのトレース）、アルゴリズムを図で表す話は第47講（アルゴリズムと流れ図）にまとめてあります。

6. 情報Ⅱではこうなる

情報Ⅰでは、計算量は「回数を数えて比べる」ところで止まります。情報Ⅱでは、それが「設計するときに何を選ぶかの基準」になります。 これは私の意見ではなく、教材の中で記述が置かれている場所がそう変わるのです。

6-1. 分析手法そのものが計算量で決まる（情報Ⅱ(3)）

3-4で引いたアソシエーション分析がそれです。組合せ爆発を避けるために、工夫のほうに名前が付きます。「一定の基準以上の支持度や確信度の場合だけ計算する」＝枝を落とす、それが「アプリオリアルゴリズム」。

情報Ⅰの「全部の2つ組を調べると n² 回」が、情報Ⅱでは「全部の組合せを調べると 2ⁿ 通りで終わらないから、基準を決めて落とす」に変わる。同じ発想が、そのまま手法の名前になっています。

同じ第3章後半の学習17（ニューラルネットワーク）では、歴史そのものが計算量で説明されています。

そして「計算処理を分散して実行できるGPUの登場と，コンピュータの計算処理速度の向上により」実用になった、と続きます。理論はあったのに、計算量が壁になって長く動かなかった。 アルゴリズムの重さが歴史を止めた実例です。

6-2. データベースの方式選択になる（情報Ⅱ(3)）

同じ教材の第3章前半、学習11「データと関係データベース」にはこうあります。

理由も書かれています。関係データベースは「データを処理するハードウェアが1台で完結することを想定していることが多く，複数のハードウェアで大量のデータを分散処理することは得意ではない」。データが増えたときに、アルゴリズムどころか「データベースの種類そのもの」を選び直す。 これが情報Ⅱの水準です。第90講（データベースの基礎）で表・レコード・キーを押さえたら、その先にこの判断が待っています。

なお「速く引くために索引（インデックス）を別に作る」という話は、情報Ⅱ教員研修用教材 第3章前半には出てきません（学習11 に「インデックス」「索引」の語はありません）。一方、IPA 基本情報技術者試験シラバス Ver.9.2 には「データベースの性能向上」として B-tree インデックス等が並びます。教材と実務のあいだには、ここでも段差がある。 主語を分けて理解しておいてください。

6-3. 非機能要件・性能テストになる（情報Ⅱ(4)）

情報Ⅱ教員研修用教材 第4章 学習24 は、非機能テストを「性能や，ユーザーが操作をしてから結果が表示されるまでの処理時間や，負荷が高まったときでも正常に動作するかなど非機能要件と呼ばれる観点でのテスト」と定義します。学習25 の性能テストは「情報システムを実際と同じように動かしてみて，要件を満たす性能が出るかどうかを確認するテスト」です。

情報Ⅰでは机の上で数えていた回数が、情報Ⅱでは「要件」になり、満たすかどうかを試験して確かめる対象になります。 第73講（通信速度とデータ量の計算）で扱った見積りの話が、ここで合流します。

6-4. 注意：情報Ⅱ(4)の「効率」は開発効率のこと

ひとつ、書き方に注意が要る点があります。学習指導要領解説 情報編の情報Ⅱ(4)に出てくる「効率」は、「情報システムをいくつかの機能単位に分割して制作し統合するなど，開発の効率や運用の利便性などに配慮して設計する」のように、開発の効率を指しています。実行速度のことではありません。

ですから「情報Ⅱでは計算量を学ぶ」と一般化して言うのは正確ではありません。正しくは、実行効率の話は情報Ⅱ(3)のデータサイエンス側と、第4章の非機能要件（性能テスト）側に分かれて置かれている、です。

まとめ

• 実行時間は機械・言語・入力で変わる。変わらないのは「n が増えたときの増え方」だけ。
• n が大きくなると最高次の項が支配する。だから定数倍と低次の項は捨ててよい。実測でも 110.00 → 100.91 → 100.09 と100に収束する。
• n を10倍したとき、log n は +3.32、n は10倍、n log n は約13.3倍、n² は100倍。2ⁿ は桁が壊れる。
• 2¹⁰⁰ は31桁。1秒1兆回でも約401.7億年。機械を1000倍速くしても n が10増えれば元通りなので、指数の壁は買い物では越えられない。
• 計算量は1つの数ではない。最悪・平均・最良で違う（線形探索 n=1,000 は 1回／500.5回／1,000回）。時間だけでなく空間（領域計算量）も測る。
• O記法は高校の一次資料に無い。記号ではなく「10倍したら何倍か」を持つこと。
• 情報Ⅱでは、計算量が「アプリオリアルゴリズム」「NoSQLの選択」「性能テスト」という設計の判断に変わる。

出典（すべて2026年8月3日に取得）

• 文部科学省「高等学校学習指導要領（平成30年告示）解説 情報編」平成30年7月
• 文部科学省「高等学校情報科『情報Ⅰ』教員研修用教材」第3章 コンピュータとプログラミング（令和2年）
• 文部科学省「高等学校情報科『情報Ⅱ』教員研修用教材」第3章 情報とデータサイエンス 前半（令和2年7月）・後半（令和2年6月）
• 文部科学省「高等学校情報科『情報Ⅱ』教員研修用教材」第4章 情報システムとプログラミング（令和2年6月）
• 情報処理推進機構（IPA）「ITパスポート試験（レベル1）シラバス Ver.6.5」「基本情報技術者試験（レベル2）シラバス Ver.9.2」「応用情報技術者試験（レベル3）シラバス Ver.7.2」（いずれも掲載2026年1月8日）
• 大手予備校の共通テスト2026「情報Ⅰ」分析（二次情報。設問構造の説明にのみ使用）

この講は『藤原進之介の最強120講義』の第3部（コンピュータとプログラミング）に入ります。全120講の一覧は情報Ⅰ 最強120講義のハブページにまとめてあります。