アルゴリズムの選択と計算量｜情報Ⅰ 最強120講義 第116講

こんにちは、数強塾代表の藤原進之介です。この記事は参考書『藤原進之介の最強120講義』の第116講「アルゴリズムの選択と計算量」のWeb版です。第6部（情報Ⅱへの橋）に入る講で、共通テストでの重要度はC——情報Ⅱは共通テストの出題科目ではないからです。

第57講（計算量の考え方）で、伸び方で測るという考え方を通しました。この講はその続きです。情報Ⅰの計算量は「どちらが速いか」の比較でしたが、情報Ⅱの計算量は「できるかできないか」の境界になります。 国の教材を全部数え、実際にプログラムを走らせて確かめた結果を書きます。

1. この講の問い

情報Ⅰの計算量は「どちらが速いか」を比べる道具だった。情報Ⅱでは、計算量は何になるのか。

2. 結論

3. なぜそうなるのか

3-1. まず、語がどこにあるかを数えました

私は学習指導要領解説 情報編と、情報Ⅰ・情報Ⅱの教員研修用教材を全部テキスト化して数えました（調べた範囲は第6章に明記します）。出てきた表がこれです。

この表は、ひとつの事実をはっきり示しています。

情報Ⅰの教材では、第3章「コンピュータとプログラミング」だけで「アルゴリズム」が49回、線形探索と二分探索が22回ずつ、流れ図が20回出ます。ところが情報Ⅱでは、プログラミングの章（第4章）の「アルゴリズム」は0。「アルゴリ」と短く切って検索しても0なので、PDFの語の分断でもありません。「手順」という別の語で書き換えられているのかとも疑いましたが、第4章の「手順」5件はバッチ処理の処理手順・モジュール分割の手順・テスト手順で、アルゴリズムの意味ではありませんでした。

代わりに、情報Ⅱ教材の「アルゴリズム」22件のうち18件が第3章後半、つまりデータサイエンスの章に集まっています。

3-2. だから「書く」から「選ぶ」に変わる

なぜ引っ越したのか。第3章後半の学習16（クラスタリングによる分類）の【研修の目的】に、はっきり書かれています。

選択する。評価する。改善する。 「作る」ではありません。
情報Ⅰでは、線形探索と二分探索を自分で書き、比較回数を数えました。情報Ⅱでは、既にあるアルゴリズムの中から場面に合うものを選び、選んだ結果を評価します。だから第4章から「アルゴリズム」が消え、第3章後半に集まるのです。

ここで大事なのは、「選ぶ」という発想そのものは情報Ⅰの側に既にあるということです。学習指導要領解説 情報編、共通教科の情報Ⅰ(3)イ(イ)にこうあります。

同じア(イ)には「アルゴリズムによって処理の結果や効率に違いが出ること」ともあります。つまり国は、情報Ⅰの段階で既に「効率を考えて選べ」と書いている。情報Ⅱで新しく足されるのは選ぶという行為ではなく、選ばないと終わらない規模のデータのほうです。

3-3. 情報Ⅱの計算量は「できるかできないか」の境界になる

情報Ⅱ教材で「計算量」が出るのは3か所だけ。そのうち中心はここです。第3章後半、学習16のアソシエーション分析。

情報Ⅰの計算量は「線形探索より二分探索が速い」という比較でした。ここでの計算量は比較ではありません。「終わるか、終わらないか」です。

そして注目してほしいのは、この文が手法の名前を導入する文になっていることです。アプリオリアルゴリズムは、新しい発見をするための道具ではありません。全部調べたら終わらないから作られた、逃げ道に付いた名前です。情報Ⅱでは、計算量が手法の存在理由そのものになっている。これが情報Ⅰとの最大の違いです。

3-4. 「速い機械を買う」では解決しない理由が、教材の中にある

「終わらないなら、速いコンピュータを使えばいい」と考えたくなります。この反論に、情報Ⅱ教材は自分の第1章で先に答えています。

計算機の性能も指数関数で伸びます。ですが、全ての組合せを調べる仕事量も指数関数です。ここで簡単な計算をしてみましょう。

商品を10種類増やすと、組合せの数は 2¹⁰ = 1,024倍になります。ムーアの法則が2年で2倍なら、1,024倍の性能を得るには 10回の倍増＝約20年（18か月なら約15年）かかります。

しかも同じ教材は、その先も書いています。

さらに同じ第1章には「コンピュータの演算速度は指数関数的に向上していくと見られている」と書きつつ、「学習1でも触れた『ムーアの法則』が今後もその通りに続いていくかどうかは議論が分かれているようであるが」という留保まで置かれています。

つまり、待っても来ないかもしれない。残るのはアルゴリズムを選ぶことだけ。 この講のタイトルが「アルゴリズムの選択と計算量」である理由はここにあります。

3-5. 「冬の時代」を正確に読む——理論の敗北ではないが、計算資源だけの話でもない

情報Ⅱ教材には「冬の時代」が6件あります。私はこの6件を1件ずつ読みました。そして、原因が2種類に分かれていることが分かりました。

第3章後半（学習17・1件）は、ニューラルネットワークの話です。

原型が発表されたのは1943年。理論のほうが半世紀先にありました。そして教材はこう続けます。「その後，計算処理を分散して実行できるGPUの登場と，コンピュータの計算処理速度の向上により重み付けの調整が人の手から離れ…（自律学習）が可能となった」。

同じ考え方が、計算機が速くなっただけで実用になった。 理論と資源の関係を、これほど短く示した文はなかなかありません。

ところが第1章（5件）の「冬の時代」は、まったく別の理由で説明されています。人工知能の第一次・第二次ブームの話です。「チェスのようなルールのある限定したもの以外では条件を付けることが難しく，冬の時代を迎えることになった」「『常識』や『抽象的な表現』を体系付けたり学習させたりすることが非常に難しく，やはり冬の時代を迎えることになった」。こちらは計算量の話ではありません。知識をどう表すかという壁です。

3-6. 「効率」という語の罠

ここが最大の落とし穴です。情報Ⅱの資料で「効率」という語を見たら、まず実行速度ではないと疑ったほうがいい。

学習指導要領解説の情報Ⅱ節（共通教科）に「効率」は4件あります。私は4件とも中身を見ました。全数がこれです。

• 「情報システムをいくつかの機能単位に分割して制作し統合するなど、開発の効率や運用の利便性などに配慮して設計する」（2件）
• 「どのような関数を利用すれば効率的な開発ができるか判断する力」
• 「効率的な経営のために必要なPOSシステム」

実行速度の意味は0件。

情報Ⅱ教員研修用教材の第4章にも「効率」は15件あります。これも15件とも見ました。開発の効率化、モジュール再利用による開発の効率化、言語を選べば効率よく目的を達成する、テストを効率的に、チームの作業効率、効率的に開発を進める工夫、在庫管理及び店舗管理の効率化、効率よく営業できる利便性——やはり実行速度の意味は0件でした。

では、情報Ⅱで実行の速さはどこへ行ったのか。別の語に引っ越しました。

• データ分析の側では「計算量」（第3章後半3件）
• 情報システムの側では「非機能」（第4章8件）と「性能テスト」（第4章6件）

第4章はこう書きます。「非機能テストと呼ばれるテストでは、プログラムの機能ではなく処理速度や反応速度など、ユーザーが操作する際に不満がないレベルのものであるかをテストしていく」。情報Ⅰでは机の上で数えていた回数が、情報Ⅱでは満たすべき要件になり、試験して確かめる対象になるのです。

3-7. なぜ情報Ⅱは df.sort_values() の1行で済ませるのか

情報Ⅰ教員研修用教材の第3章は、整列を自分で書かせます。比較回数も数えさせます。ところが情報Ⅱ教員研修用教材の第3章前半 学習12 は、都道府県の人口増減率を並べ替えるところを、こう済ませます。

中身は一切書きません。 どんな整列アルゴリズムが動いているかも書きません。情報Ⅱ教材で「線形探索」「二分探索」が0件、「流れ図」「フローチャート」が0件になるのはこのためです。

これは手抜きではありません。道具として使う段階に来ているからです。データ分析の主題は「どう並べ替えるか」ではなく「並べ替えて何を見るか」。毎回ソートを自作していたら分析は進みません。

そして面白いことに、国はその穴を別の場所で埋めています。

文部科学省が公開している高等学校「情報Ⅰ」オンライン学習会 第7回（令和5年1月27日実施、講師：大阪電気通信大学 教授・副学長 兼宗進）の配付資料に、「大量のデータを扱うアルゴリズム（整列）」というスライドがあります。そこにはこう書かれています。

O記法です。 第57講で私は「O記法は高校の一次資料には無い」と書きましたが、これは正確には学習指導要領解説と教員研修用教材の範囲での話でした。文部科学省が同じサイトに置いている研修資料には、O(n²) がはっきり書かれています。訂正します。

しかもこの資料はほぼ全ページが画像で、テキスト抽出では9MBのPDFから6KBしか取れません。全文検索では見つかりません。私は該当ページを画像として開いて目で確認しました。「一次資料に0件」という主張が、いかに壊れやすいかの実例です。この本の空白リストには、この限界を必ず注記します。

4. 手で確かめる

4-1. まず教材の8枚のレシートを自分で計算し直す

情報Ⅱ教員研修用教材 学習16 は、8枚のレシートでマーケットバスケット分析を説明します。

指標は3つ。支持度は全レシート8枚のうち何枚に入っていたか。確信度は X を買った人のうち Y も買った割合。リフト値は確信度を Y の支持度で割った値です。

数えるだけで確かめられます。コーヒーは4枚（1・2・3・4）、パンは5枚（1・2・3・5・8）、弁当は7枚、お茶と紅茶は2枚ずつ。

• supp(コーヒーとパン) = 3/8 = 0.375（1・2・3）
• conf(コーヒー→パン) = 3/4 = 0.75
• lift(コーヒー→パン) = 0.75 ÷ (5/8) = 6/5 = 1.2
• lift(コーヒー→弁当) = 0.75 ÷ (7/8) = 6/7 ≒ 0.857

教材の数値と一致します。リフト値が1より大きいと「一緒に買われやすい」、1を下回ると「推奨する根拠になりにくい」。

4-2. 教材の解答例に1か所ずれがあります

演習4は「パンを買った人に薦めるものを検討しましょう」です。私は先に自分で計算しました。

そのうえで文部科学省が公開している演習解答（第3章 学習16 演習4）を見たところ、弁当の行の supp(パンと弁当) が 3/8＝0.375 と書かれていました。パンと弁当が両方入っているレシートは 1・2・5・8 の4枚なので、正しくは 4/8 = 0.5 です。

これは表の中だけで矛盾が証明できます。確信度は supp(パンと弁当) ÷ supp(パン) ですから、もし 3/8 なら (3/8)÷(5/8) = 3/5 = 0.6 になるはずです。ところが同じ行の確信度は 4/5 = 0.8 と書かれている。同じ行の2つの数が両立しません。 おそらく1つ上のコーヒーの行からの転記ミスでしょう。

責める話ではありません。指標を3つ手で計算するだけで、国の資料の誤記に自力で気づけるという話です。結論（薦めるのはリフト値の高いコーヒー）は変わりません。

4-3. 組合せの数を並べる

商品が n 種類あるとき、空でない組合せ（アイテム集合）の数は 2ⁿ − 1。X→Y の形のルールの数は 3ⁿ − 2ⁿ⁺¹ + 1 です。

上の例は商品が5種類だったので、組合せは 2⁵ − 1 = 31 通りしかありません。手で全部書けます。商品が30種類になると10億通り。50種類で1,000兆通り。 教材が言う「実際には商品は膨大な種類がある」は、この列のことです。

（式は n = 3, 4, 5, 10 で実際に全列挙して照合しました。たとえば n=10 なら列挙1,023／式1,023、ルールは列挙57,002／式57,002 で一致します。）

4-4. 全探索を本当に走らせてみる

数字を眺めるだけでは足りません。実際に走らせました。レシート300枚を固定の乱数種で作り、全ての空でないアイテム集合の支持度を数えるプログラムを、n を変えて回します。

def brute(n, T):
    checked = 0
    for s in range(1, 1 << n):        # 空でない全ての組合せ
        checked += 1
        c = 0
        for t in T:                   # 全レシートを見る
            if t & s == s:
                c += 1
    return checked

実行結果（2026年8月3日、当方の Python 3、レシート300枚）。

n=10  調べた集合 1,023            0.012 秒
n=12  調べた集合 4,095            0.039 秒   n+2 で 3.42倍
n=14  調べた集合 16,383           0.146 秒   n+2 で 3.71倍
n=16  調べた集合 65,535           0.604 秒   n+2 で 4.14倍
n=18  調べた集合 262,143          2.583 秒   n+2 で 4.28倍
n=20  調べた集合 1,048,575       10.205 秒   n+2 で 3.95倍

n が2増えるたびに、きれいに約4倍（＝2²倍）。 これが指数の顔です。n=20 の 10.205 秒を基準に、+10 ごとに 1,024倍として外挿するとこうなります。

商品60種類。コンビニの棚1本分にも足りません。それで35万年です。教材の「計算時間も現実的な時間で収まらなくなる」は、比喩ではありません。

4-5. 枝刈りを実装して、探索数を数える

アプリオリの発想はひとことで言えます。

コーヒーが100枚中3枚にしか出ないなら、「コーヒーとパン」は3枚以下、「コーヒーとパンと弁当」はもっと少ない。だから、コーヒーが落ちた時点で、コーヒーを含む組合せは全部まとめて捨ててよい。 数える必要すらありません。

これを実装して、同じデータで比べました。最小支持度は5%（300枚中15枚以上）。

n=10  全探索 1,023        集合 0.010 秒  →  アプリオリ 108 集合 0.0015 秒（9分の1）
n=15  全探索 32,767       集合 0.320 秒  →  アプリオリ 145 集合 0.0019 秒（226分の1）
n=20  全探索 1,048,575    集合 10.407 秒  →  アプリオリ 229 集合 0.0030 秒（4,579分の1）

n=20 で、104万個を調べていたのが229個になりました。約4,579分の1。 そして最も大事な検算がこれです。

頻出集合 54 個（サイズ別 20 / 29 / 5）  答えの一致: 完全一致

枝刈りをしても、見つかる頻出集合は全探索と1つも違いません。 減ったのは仕事量だけで、答えは減っていない。これがアルゴリズムの工夫というものの正体です。

しかも n が大きいほど効きます。全探索は 2ⁿ で伸びるのに、アプリオリが調べた数は 108 → 145 → 229 とほとんど増えていません。指数を、データの中身に応じた小さな数に取り替えているのです。

図1でいえば、{A,B} の1回の判定で {A,B,C}・{A,B,D}・{A,B,C,D} の3つが消えました。商品が n 種類あるとき {A,B} を含む集合は 2ⁿ⁻² 個あるので、n=20 なら 262,144個が一度に落ちます。これが「4,579分の1」の中身です。

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

この講は共通テストへの接続がありません。 情報Ⅱは共通テストの出題科目ではないからです。

大学入試センターが公表している「令和9年度大学入学者選抜に係る大学入学共通テスト 出題教科・科目の出題方法等」を見ると、教科「情報」の出題科目は 『情報Ⅰ』の1つだけで、60分・100点です。同じ資料の備考には「『 』は大学入学共通テストにおける出題科目を表し、「 」は高等学校学習指導要領上設定されている科目を表す」とあり、『情報Ⅱ』という出題科目は存在しません（2026年8月時点）。

では、ここまでの話は受験に無関係かというと、そうではありません。第55講（探索）・第56講（整列）・第57講（計算量）が伸びる先がここだからです。情報Ⅰの共通テストで問われるのは「線形探索と二分探索のどちらが有利か」「処理回数をどう減らすか」という比較です。その比較の基準（伸び方で見る、最悪で見る、前処理のコストも足す）は第57講で扱いました。本講が足すのは、その基準が最後にどこへ行き着くかという見通しです。比較の話が、いつか「そもそも終わるのか」という話に変わる。その入口を知っている受験生は、目の前の「処理回数を減らす」設問の意味が違って見えます。

6. 情報Ⅱではこうなる

この講そのものが情報Ⅱの話なので、ここには調べた範囲の宣言と、情報Ⅰ→情報Ⅱの対応をまとめます。

6-1. 調べた範囲（「0件」の意味を限定するために明記します）

• 高等学校学習指導要領解説 情報編（平成30年7月）。第1部＝共通教科（第1章総説／第2章第1節 情報Ⅰ／第2節 情報Ⅱ／第3章）と第2部＝主として専門学科で開設される教科「情報」を分けて計数
• 情報Ⅰ教員研修用教材（令和2年）巻頭＋第1〜4章の全分冊
• 情報Ⅱ教員研修用教材（令和2年6月・7月）序章・第1章・第2章・第3章前半・第3章後半・第4章・第5章の全7分冊（第3章が前半・後半の2分冊であることに注意）
• 情報Ⅱ教員研修用教材 第3章 演習解答（別PDF）
• 文部科学省 高等学校「情報Ⅰ」オンライン学習会 第7回 配付資料

いずれも Unicode正規化のうえ空白と改行を全て除去してから計数し、ヒットは1件ずつ前後を目で読んで用法を確認しました。それでも「0件」は「テキスト抽出できた範囲で0件」でしかありません。 3-7で書いたとおり、O記法は画像PDFの中に実在しました。

6-2. 素朴に数えると間違える語（本講で新たに2つ見つけました）

• 「NP」：情報Ⅱ教材 第3章後半に2件ヒットしますが、2件とも「INPUT」の一部。NP問題は0件です
• 「多項式」：解説の共通教科側に1件、情報Ⅱ教材 第3章前半に2件ありますが、全て回帰の近似曲線・二次多項式モデル。多項式時間の意味は0件です

6-3. 情報Ⅰと情報Ⅱの対応

6-4. 第57講の記述を2か所訂正します

本書は自分の誤りを消さずに訂正する方針なので、はっきり書いておきます。

• 「O記法は高校の一次資料には無い」 → 正しくは「学習指導要領解説と教員研修用教材には無い」。文部科学省が公開している研修資料（オンライン学習会 第7回）には O(n²) が明記されています
• 「共通教科（情報Ⅰ・Ⅱ）には無い『アルゴリズムの効率化』が専門教科の側に書かれている」 → 「アルゴリズムの効率化」「効率的なアルゴリズム」が専門教科側にあるのは正しいのですが、「アルゴリズムの効率を考える力」「適切にアルゴリズムを選択する力」は情報Ⅰ（共通教科）の解説に明記されています。共通教科に効率の観点が無いわけではありません

まとめ

• 情報Ⅱ教材の第4章（プログラミングの章）に「アルゴリズム」が0件。22件のうち18件がデータサイエンスの章に移っている。アルゴリズムは書くものから選ぶものになった
• 情報Ⅰの計算量は「どちらが速いか」。情報Ⅱの計算量は「終わるか終わらないか」。だから工夫のほうに名前が付く（アプリオリアルゴリズム）
• 商品を10種類増やすと組合せは1,024倍。ムーアの法則15〜20年分が一度に消える。 しかも教材自身が微細化の限界と「議論が分かれている」と書いている
• 実測：n が2増えるごとに全探索は約4倍。n=60 の全探索は外挿で約35万年。アプリオリの枝刈りで n=20 は 4,579分の1、しかも答えは全探索と完全一致
• 「冬の時代」の原因は1つではない。ニューラルネットワークは計算量とアルゴリズム、AI全体は知識表現。教材は書き分けている
• 情報Ⅱの「効率」は開発の効率。解説 情報Ⅱ節4件・教材第4章15件を全数確認して実行速度の意味は0件だった。実行の速さは「計算量」「非機能」「性能テスト」へ引っ越した
• df.sort_values() の1行は道具として正しい。ただし中身を知らないと、遅くなった日に手が出ない

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

• 文部科学省「高等学校学習指導要領（平成30年告示）解説 情報編」平成30年7月
• 文部科学省「高等学校情報科『情報Ⅱ』教員研修用教材」序章・第1〜5章（第3章は前半・後半の2分冊。令和2年6月・7月）／同 第3章 演習解答https://www.mext.go.jp/a_menu/shotou/zyouhou/detail/mext_00742.html
• 文部科学省「高等学校情報科『情報Ⅰ』教員研修用教材」巻頭・第1〜4章（令和2年）
• 文部科学省 高等学校「情報Ⅰ」オンライン学習会【第7回】アルゴリズムの比較から効率的なアルゴリズムの理解の仕方（令和5年1月27日実施、講師：大阪電気通信大学 教授・副学長 兼宗進）https://www.mext.go.jp/a_menu/shotou/zyouhou/detail/mext_02128.html
• 大学入試センター「令和9年度大学入学者選抜に係る大学入学共通テスト 出題教科・科目の出題方法等」（令和7年6月6日公表）https://www.dnc.ac.jp/kyotsu/shiken_jouhou/r9/

この講は『藤原進之介の最強120講義』の第6部（情報Ⅱへの橋）に入ります。第6部の入口は第109講（情報Ⅱの全体像）、データ分析の手順は第110講（データサイエンスのワークフロー）です。全120講の一覧は情報Ⅰ 最強120講義のハブページにまとめてあります。