※小説ではない※専門書 要約資料集 為替(換算)3.9万円でもらう 紐解集生成 専門 初入門 資料 作：｛作者名｝
> 学問の宇宙・応用の軌道ステーション群(情報工学)派生章。ガイド役: Fable 5 監修 / Sonnet 5 執筆(脚本班)
> トーン規約: GAKUMON_UNIVERSE.md準拠。専門用語は初出で必ず説明する。
# BOOK-0066 アルゴリズムとデータ構造 — 「手順」という発明の階段(第1巻)
> 学問の宇宙・応用の軌道ステーション群(情報工学)派生章。ガイド役: Fable 5 監修 / Sonnet 5 執筆(脚本班)
> トーン規約: GAKUMON_UNIVERSE.md準拠。専門用語は初出で必ず説明する。
---
## 入口の物語 — 「レシピ」という発明
台所を思い浮かべてほしい。カレーを作るとき、材料を適当な順番で鍋に放り込んでも、なんとなく食べられるものはできるかもしれない。しかし「玉ねぎを飴色になるまで炒めてから肉を加え、水を入れて煮込み、最後にルーを溶かす」という**手順**を守ると、同じ材料からずっと美味しいカレーが、しかも毎回同じ品質で作れる。この「材料は同じでも、手順を変えると結果が変わる」という事実こそが、この冊子全体を貫く主題である。
情報工学(じょうほうこうがく、水準一: 情報を扱う仕組み——計算・記憶・通信——を作り出す学問)の世界では、この「手順」のことを**アルゴリズム(algorithm、水準一: ある問題を解くための、有限個の明確な手順の集まり)**と呼ぶ。アルゴリズムは、料理のレシピにとてもよく似ている。レシピが「材料(入力)」を受け取り、「手順(処理)」を経て、「料理(出力)」を生み出すように、アルゴリズムは「データ(入力)」を受け取り、「計算の手順(処理)」を経て、「答え(出力)」を生み出す。→BOOK-0010『コンピュータの始まり』第1冊で見たように、コンピュータは「0と1」という最小の言葉で動く機械だが、その機械に「何をどの順番でやらせるか」を決めているのが、まさにこのアルゴリズムなのである。
なぜアルゴリズムの話が面白いのか。それは、同じ「答えにたどりつく」という目的でも、手順の選び方次第で、かかる時間が一瞬にも、宇宙の年齢よりも長くにもなりうるからだ。この冊子では、「探す」「並べる」という二つのごく身近な作業を題材に、手順の工夫がどれほど劇的な差を生むかを、実際の数を使って検算しながら確かめていく。そのあとで、データそのものの「置き方」を工夫する道具箱——データ構造——を見て、最後に「手順の良し悪しをどう測るか」という物差し、計算量の入口にたどりつく。
---
## 第一章: アルゴリズムとは何か — レシピという発明の歴史
### 「手順を書き残す」という発想の古さ
「決まった手順に従えば、誰がやっても同じ結果にたどりつける」という発想そのものは、実はコンピュータよりもはるかに古い。現存する記録の中でも特に古典的とされる例が、**ユークリッドの互除法(ごじょほう、水準一: 二つの整数の最大公約数を、割り算の繰り返しだけで求める手順)**である。これは古代ギリシャの数学者ユークリッドの著書『原論』(紀元前300年ごろ)に記されている手順で、最大公約数(二つの整数を割り切れる、最大の共通の数)を求めるための方法として、現在でも「最古級のアルゴリズム」として紹介されることが多い。
ユークリッドの互除法の手順を、日本語の言葉で書き下すと次のようになる。
```
手順(ユークリッドの互除法):
1. 二つの整数 A, B (A > B) を用意する
2. A を B で割った余り R を求める
3. R が 0 なら、B が最大公約数。手順を終了する
4. R が 0 でなければ、A に B の値を、B に R の値を入れ直して、手順2に戻る
```
具体的な数で確かめてみよう。48と18の最大公約数を求める場合、48を18で割ると商2・余り12。次に18を12で割ると商1・余り6。次に12を6で割ると商2・余り0。余りが0になったので、最大公約数は6である(実際、48=6×8、18=6×3で、6が最大の共通の割り切れる数になっている)。この「割り算を繰り返すだけで、掛け算の分解(素因数分解)をしなくても最大公約数が求まる」という手順の賢さこそが、このアルゴリズムが二千年以上生き延びてきた理由である。
### アル=フワーリズミー — 「アルゴリズム」という言葉の由来
「アルゴリズム」という言葉そのものの語源には、9世紀の数学者**アル=フワーリズミー(al-Khwarizmi、諸説あるが780年ごろ - 850年ごろ、現在のウズベキスタン付近の出身とされる)**の名前が関わっている、というのが広く紹介されている説である。アル=フワーリズミーはバグダードの「知恵の館」と呼ばれる学術機関で活動し、インド由来の十進の数字表記法や計算手順を体系的にまとめた著作を残した人物として知られる。彼の名前(ラテン語表記で Algoritmi)が、ヨーロッパに数の計算手順が伝わる過程で「algorism(のちに algorithm)」という単語に姿を変えていった、というのが一般的に紹介される語源説明である。ただし、語源の細部——どの著作のどの時点でどう転訛したか——については研究者ごとに説明の重点が異なる部分があり、本書では「アル=フワーリズミーの名が語源の中心にある」という広く共有された大枠を採り、細部は**諸説あることを明記**しておく。
また、彼の別の著作の題名(代数的な方程式の解法を扱ったもの)からは、「代数(algebra)」という単語も生まれたとされる。一人の数学者の名前と著作から、「algorithm」と「algebra」という、現代の数学と情報科学を支える二つの単語がともに派生した、というのは、歴史のいたずらのような面白さがある。
### 手順に必要な「良い条件」
アルゴリズムと呼べるためには、ただの手順書ではなく、いくつかの条件を満たす必要がある、としばしば整理される。代表的には「①手順が有限回で必ず終わること(いつまでも終わらない手順は困る)」「②各手順が曖昧でなく、機械的に実行できるほど明確であること」「③同じ入力を与えれば、同じ手順で同じ結果にたどりつくこと」の3点である。ユークリッドの互除法は、余りが必ず小さくなっていき、いずれ0に到達することが保証されているため、①の条件を満たす良いアルゴリズムの典型例として、教育の場でもよく引き合いに出される。
料理のレシピに戻れば、「塩少々」のような曖昧な指示はアルゴリズムには向かない。「塩を2グラム加える」のように、誰が読んでも同じ動作にたどりつける明確さこそが、レシピをアルゴリズムたらしめる条件なのである。
### エイダ・ラヴレスと解析機関のノート
アルゴリズムの歴史を語るうえで欠かせないもう一人の人物が、**エイダ・ラヴレス(Ada Lovelace、1815年 - 1852年)**である。ラヴレスは数学者チャールズ・バベジが構想した**解析機関(かいせききかん、水準一: バベジが19世紀に構想した、歯車とパンチカードを使う汎用計算機の設計。実際に完成することはなかった)**について、**1843年**にフランス語の論文を英訳し、そこに自身の詳細な注釈(ノート)を付け加えた。このノートの中で、ラヴレスは解析機関を使ってベルヌーイ数(数学で使われる特定の数列)を計算するための、一連の手順を具体的に書き記した。
この注釈は、機械がまだ実際には動いていない段階で、「機械に実行させる具体的な計算手順」を体系立てて書き残した、非常に早い記録として紹介されることが多く、そのためラヴレスは「世界初のプログラマー」と呼ばれることがある(この呼称の当否については、機械そのものが未完成だったこと、当時の他の研究との関係などから、歴史家の間で議論があることも申し添えておく)。いずれにせよ、「計算機に何をどんな順番でやらせるか」を紙の上で設計するという行為が、コンピュータ本体が実際に動くよりも100年近く前から始まっていたという事実は、アルゴリズムという概念が「機械」よりも先に「発想」として存在していたことを鮮やかに示している。
---
## 休憩所①: まとめ箱 — 第一章の要点
- アルゴリズムとは「有限の明確な手順で問題を解く」設計図。料理のレシピが良い比喩になる。
- ユークリッドの互除法(紀元前300年ごろの記録)は最古級のアルゴリズムとされ、割り算の繰り返しだけで最大公約数を求める。
- 「アルゴリズム」の語源は9世紀の学者アル=フワーリズミーの名前に由来するというのが広く紹介される説(語源の細部は諸説あり)。
- エイダ・ラヴレスは1843年、解析機関のための計算手順をノートに書き記し、機械が完成する前から「手順の設計」という営みを実践した。
---
## 第二章: 探索 — 「探す」という作業を賢くする
### 線形探索 — 端から順に見ていく、最も素直な方法
いま、本棚に1000冊の本が、著者名の順に並んでいない(バラバラな順序の)状態で並んでいるとしよう。この中から特定の1冊を探すとき、もっとも素朴な方法は、端から一冊ずつ確認していくことである。これを**線形探索(せんけいたんさく、水準一: データの先頭から順番に一つずつ確認していき、目的のものを見つける探索方法)**と呼ぶ。
線形探索の手順は単純そのものである。
```
手順(線形探索):
1. 先頭のデータを見る
2. 探しているものと一致すれば、見つかったので終了
3. 一致しなければ、次のデータに進んで手順1に戻る
4. 最後まで見て見つからなければ「存在しない」と判定して終了
```
この方法の利点は、データが並んでいる順序を問わないことである。バラバラに積まれた本の山からでも、最悪でも全部の本を1回ずつ確認すれば、必ず目的の本にたどりつける(あるいは「ない」と確定できる)。ただし、本の冊数が増えるほど、最悪の場合に確認しなければならない回数も比例して増えていく。1000冊なら最大1000回、100万冊なら最大100万回の確認が必要になる、というのが線形探索の限界である。
### 二分探索 — 「並んでいる」ことを武器にする
もし本棚の本が、著者名のあいうえお順(あるいはアルファベット順)にきちんと並んでいたらどうだろうか。このとき使えるのが**二分探索(にぶんたんさく、水準一: 並び順に整列されたデータに対して、真ん中の要素と比較しながら探索範囲を半分ずつに絞り込んでいく探索方法)**である。
```
手順(二分探索):
1. 探索する範囲全体の「真ん中」のデータを見る
2. 探しているものと一致すれば、見つかったので終了
3. 探しているものが真ん中より前(小さい)なら、範囲を前半だけに絞る
4. 探しているものが真ん中より後(大きい)なら、範囲を後半だけに絞る
5. 絞り込んだ範囲に対して、手順1に戻る(範囲が空になったら「存在しない」と判定)
```
辞書で単語を引くとき、私たちは無意識のうちにこれに似た動きをしている。辞書の真ん中あたりを開き、探している単語がそれより前か後かを見て、次にめくる場所を大きく絞り込む——これはまさに二分探索の考え方そのものである。
### 数値検算① — 1024件の本を、二分探索なら最大何回で探せるか
二分探索の強さを、具体的な数で確かめてみよう。整列済みのデータが**1024件**あるとする。二分探索では、1回の比較ごとに探索範囲が半分になる。
```
1024件 → (1回目の比較後) 512件
512件 → (2回目) 256件
256件 → (3回目) 128件
128件 → (4回目) 64件
64件 → (5回目) 32件
32件 → (6回目) 16件
16件 → (7回目) 8件
8件 → (8回目) 4件
4件 → (9回目) 2件
2件 → (10回目) 1件 ← ここで確定
```
1024件から始めて、範囲が1件に絞り込まれるまでにちょうど**10回**の比較で済む。これは偶然の数字ではなく、2を10回掛け合わせると1024になる、つまり **2^10 = 1024** という関係の裏返しである。逆に言えば、二分探索で「最大N回の比較で探索が終わる」とき、探索できるデータの件数は最大で **2^N 件**まで、という対応関係になっている。線形探索であれば1024件の探索には最悪1024回の確認が必要だったことを思えば、二分探索の10回という数字がいかに劇的な差か分かるだろう。データが2倍の2048件に増えても、二分探索の回数はたった1回(11回)しか増えない。これが、次章で見る「計算量」という考え方の、最初の具体的な手触りである。
### 探索方法を選ぶという判断そのものが設計
ここで重要なのは、「二分探索のほうが線形探索より偉い」という単純な優劣の話ではない、ということだ。二分探索は「データが整列されている」という条件が満たされて初めて使える。整列されていないデータに二分探索は使えないし、そもそもデータを整列させる作業そのものにもコスト(手間)がかかる。「探すたびに何度も使うデータなら、先に整列しておいて二分探索を使う方が得」「一度きりしか探さないデータなら、整列の手間をかけずに線形探索で済ませる方が得」というように、状況に応じてどちらの手順を選ぶかを判断すること自体が、アルゴリズムを学ぶことの実践的な価値なのである。
---
## 休憩所②: まとめ箱 — 第二章の要点
- 線形探索は先頭から順に確認する素直な方法。整列を問わないが、データ数に比例して確認回数が増える。
- 二分探索は整列済みデータに対し、真ん中との比較で範囲を半分ずつに絞る。
- 検算: 1024件のデータは、2^10=1024 の関係により、二分探索なら最大10回の比較で探索が終わる。
- どちらを選ぶかは「データが整列済みか」「何度も探すか」といった状況次第の設計判断である。
---
## 第三章: 整列 — 「並べる」という作業を工夫する
探索の章で見たように、データが整列されているだけで、探す作業は劇的に速くなる。では、バラバラなデータをどうやって整列された状態に持っていくのか。ここからは**整列アルゴリズム(せいれつアルゴリズム、水準一: バラバラな順序のデータを、大小関係などの決まった順序に並べ替える手順)**、いわゆる「ソート」の考え方を見ていく。
### 選択ソート — 「一番小さいものを選んで前に出す」を繰り返す
トランプのカードが手元にバラバラに並んでいるとき、多くの人が自然にやる方法がこれに近い。**選択ソート(せんたくソート、水準一: 未整列部分の中から最小〈または最大〉の値を探し、それを未整列部分の先頭と入れ替えることを繰り返す整列方法)**の手順は次の通りである。
```
手順(選択ソート):
1. 未整列部分(最初は全体)の中から、最も小さい値を探す
2. 見つけた最小値を、未整列部分の先頭と入れ替える
3. 未整列部分の範囲を1つ縮める(整列済みの部分が1つ増える)
4. 未整列部分が残っていれば手順1に戻る。空になったら終了
```
例えば [5, 2, 8, 1, 9] という並びなら、まず全体から最小値の1を探して先頭と交換し [1, 2, 8, 5, 9]、次に2番目以降から最小値の2を探すがすでに正しい位置にあるのでそのまま、次に3番目以降から最小値の5を探して8と交換し [1, 2, 5, 8, 9]……というように、「未整列の中の最小を確定させていく」動きを繰り返す。
### 挿入ソート — 「トランプを手札に差し込む」ように並べる
**挿入ソート(そうにゅうソート、水準一: 整列済み部分に、未整列の要素を一つずつ適切な位置に挿入していく整列方法)**は、トランプゲームで配られたカードを手札に並べ替える動作にとても近い。
```
手順(挿入ソート):
1. 整列済み部分(最初は先頭の1枚だけ)を用意する
2. 未整列部分から次の1つを取り出す
3. 取り出した値を、整列済み部分の正しい位置に挿入する(必要な分だけ既存の要素を後ろにずらす)
4. 未整列部分が残っていれば手順2に戻る。空になったら終了
```
すでにほとんど整列されているデータに対しては、挿入ソートは非常に効率よく動く(ほとんどのカードがすでに正しい位置に近いので、差し込む手間が少ない)という性質があり、これは選択ソートにはない挿入ソートの強みとしてよく紹介される。
### マージソート — 「分割して征服する」という発想の転換
選択ソートも挿入ソートも、直感的で分かりやすい一方、データの件数が増えると手間が急激に増えていく、という弱点を共有している。この弱点を克服するために編み出されたのが、**マージソート(併合〈へいごう〉ソート、水準一: データを半分ずつに分割し、それぞれを整列してから、整列済みの二つの列を一つに統合〈マージ〉する整列方法)**である。
```
手順(マージソート):
1. データが1個以下なら、すでに整列済みとみなして終了
2. データを前半と後半、ほぼ半分ずつに分割する
3. 前半に対して、この手順(1〜4)を再び適用して整列する
4. 後半に対しても同様にこの手順を再び適用して整列する
5. 整列された前半と後半を、先頭同士を比べながら1つの列に統合〈マージ〉する
```
手順3・4で「この手順自身をもう一度呼び出す」という書き方をしている点に注目してほしい。これは**再帰(さいき、水準一: ある手順の中で、その手順自身をより小さな問題に対して呼び出す考え方)**と呼ばれる発想で、「大きな問題を、同じ形をした小さな問題に分割し、小さな問題を解いてから組み合わせる」という戦略の代表例である。この「分割して統治する(分割統治法)」という考え方は、大きな仕事を小さな班に分担させ、それぞれの成果を最後に統合する、組織的な仕事の進め方にも通じる発想だと言える。
統合(マージ)の手順そのものは単純である。整列済みの二つの列がそれぞれ手元にあるとき、両方の列の先頭同士を比較し、小さいほうを取り出して結果の列に追加する、という操作を繰り返すだけで、二つの整列済みの列を一つの整列済みの列に組み立てることができる。
### 数値検算② — マージソートは、単純な方法よりどれだけ比較回数が少ないか
整列アルゴリズムの効率を比べるとき、「データの比較を何回行うか」という回数がよく使われる目安になる。ここでは1024件のデータを例に、選択ソートに近い「単純な比較ベースの方法」とマージソートの比較回数の目安を概算してみる。
選択ソートでは、未整列部分から最小値を探すために、1回目は1023回、2回目は1022回……というように比較が必要で、これをおおまかに合計すると、件数を N として **およそ N×(N-1)÷2 回**の比較が必要になる、という目安が広く紹介されている。N=1024で計算すると、1024×1023÷2 = **約52万3776回**という、非常に大きな比較回数になる。
一方マージソートでは、「データを半分に分ける」という分割を、1024件が1件になるまで繰り返す回数が、二分探索のときと同じ **log2(1024) = 10 回**であり、各段階での統合(マージ)作業に必要な比較がおおむねデータ全体の件数(1024件)程度で済むため、全体の比較回数の目安は **およそ N×log2(N) 回**、つまり 1024×10 = **約1万240回**という概算になる。
同じ1024件のデータを整列するのに、単純な方法ではおよそ52万回、マージソートではおよそ1万回程度という概算であり、その差はおよそ**50倍**にもなる。件数が増えれば増えるほど、この差はさらに開いていく——N×(N-1)÷2 は件数の2乗に近い勢いで増えるのに対し、N×log2(N) は件数が増えても log2(N) の部分の増え方がゆるやかだからである。この「工夫された手順は、件数が増えるほど雪だるま式に有利になる」という性質こそ、次章で見る計算量という考え方が明らかにしてくれる本質である。
### クイックソート — 「基準値」で分けてから並べる
もう一つ、実務で広く使われる整列アルゴリズムとして**クイックソート(quicksort、水準一: 基準となる値〈ピボット〉を1つ選び、それより小さいものと大きいものに分けてから、それぞれを再帰的に整列する整列方法)**を紹介しておきたい。クイックソートは、イギリスの計算機科学者**チャーリー・アントニー・リチャード・ホーア(C. A. R. Hoare)**が**1960年ごろ**に考案したとされ、確実な範囲で言えば1960年前後に発表・実用化が進んだ手法として広く紹介されている(細かな発表年や経緯については資料によって記述の粒度が異なるため、ここでは「1960年ごろ」という大枠にとどめる)。
```
手順(クイックソートの考え方):
1. データの中から基準値(ピボット)を1つ選ぶ
2. 残りのデータを、基準値より小さいグループと、基準値より大きいグループに分ける
3. 小さいグループに対して、この手順(1〜4)を再び適用する
4. 大きいグループに対しても同様にこの手順を再び適用する
5. 「整列された小さいグループ」「基準値」「整列された大きいグループ」の順に並べれば完成
```
マージソートが「まず半分に割ってから、後で統合する」のに対し、クイックソートは「基準値との大小で先に振り分けてから、それぞれを整列する」という順序の違いがある。どちらも「分割統治法」という同じ大きな戦略のもとにありながら、分割の仕方が異なる、という対比で理解すると覚えやすい。
---
## 休憩所③: まとめ箱 — 第三章の要点
- 選択ソートは「未整列部分から最小を選んで前に出す」を繰り返す。
- 挿入ソートは「トランプを手札に差し込む」ように、整列済み部分へ1つずつ挿入していく。
- マージソートは「分割して統治する(分割統治法)」の代表例で、半分に割ってから統合する。再帰という考え方の典型例でもある。
- 検算: 1024件で比較すると、単純な方法(約N×(N-1)÷2 ≒ 52万3776回)とマージソート(約N×log2(N) ≒ 1万240回)の差はおよそ50倍。
- クイックソートはホーアが1960年ごろに考案したとされる、基準値で振り分けてから整列する方法。
---
## 第四章: データ構造 — 「入れ物」の工夫という発想
ここまではデータを「どう探すか」「どう並べるか」という手順(アルゴリズム)を見てきた。しかし、手順と同じくらい重要なのが、データそのものを**どんな入れ物に収めるか**という工夫、すなわち**データ構造(データこうぞう、水準一: データを効率よく扱えるように整理して収める、記憶上の入れ物の設計)**である。→BOOK-0006『OS』第1冊で見た、コンピュータがメモリという記憶領域をどう管理するかという話とも深く関わる領域である。
### 配列 — 番地の順に並んだロッカー
**配列(はいれつ、水準一: 同じ種類のデータを、連続した番地〈インデックス〉に並べて収める、もっとも基本的なデータ構造)**は、番号のついたロッカーが横一列に並んでいる様子を思い浮かべると分かりやすい。ロッカーの番号(インデックス)さえ分かれば、その中身に一瞬でアクセスできる、というのが配列の最大の強みである。二分探索が「真ん中」に一瞬でアクセスできることを前提にしていたのは、データが配列のような入れ物に収まっていることが背景にある。
一方で配列には弱点もある。ロッカーが隙間なく並んでいるため、途中に新しいロッカーを1つ挿入したければ、それより後ろのロッカー全部を1つずつ後ろにずらす必要がある。この「途中への挿入・削除が手間」という弱点を補うのが、次に見るリストである。
### 連結リスト — 「次はどこか」を手紙でつなぐ
**連結リスト(れんけつリスト、水準一: 各データが「次のデータの場所」を示す情報〈ポインタ〉を持つことで、鎖のようにつながったデータ構造)**は、宝探しの手紙に似ている。1通目の手紙に「次の手紙は木の下」と書かれていて、木の下の手紙には「次は橋の下」と書かれている……というように、それぞれのデータが「次はどこにあるか」という情報だけを持ち、鎖状につながっている。
連結リストの利点は、途中への挿入や削除が、周りの「次はどこか」という情報を書き換えるだけで済み、配列のようにデータを大量にずらす必要がない点にある。一方で、配列のように「何番目のデータか」で一瞬にアクセスすることはできず、先頭から手紙をたどっていく必要がある、という弱点がある。配列と連結リストは、「一瞬でアクセスできるが挿入・削除が重い」対「挿入・削除は軽いがアクセスは順番にたどる必要がある」という、きれいな対比関係にある。
### スタック — 「後入れ先出し」の重箱
**スタック(stack、水準一: 最後に入れたデータを最初に取り出す〈後入れ先出し、LIFO〉というルールでデータを出し入れするデータ構造)**は、重箱にお皿を積み重ねていく様子に似ている。一番最後に積んだお皿が、一番最初に取り出される。ブラウザの「戻る」ボタンが、直前に見ていたページから順に戻っていく仕組みも、スタックの考え方が使われている代表例としてよく紹介される。
### キュー — 「先入れ先出し」の行列
**キュー(queue、水準一: 最初に入れたデータを最初に取り出す〈先入れ先出し、FIFO〉というルールでデータを出し入れするデータ構造)**は、スーパーのレジに並ぶ行列そのものである。先に並んだ人が先に会計を済ませる。印刷待ちの書類が、依頼された順番に処理されていく仕組みも、キューの考え方の身近な例である。
スタックとキューは、どちらも「入れる場所」と「取り出す場所」に制約がある入れ物だが、その制約の違い(後入れ先出しか、先入れ先出しか)によって、向いている用途がまったく異なる、という点が面白い。
### 木構造 — 枝分かれで表す「親子関係」
**木構造(きこうぞう、水準一: 1つの根〈ルート〉から枝分かれして、複数の節〈ノード〉が親子関係でつながるデータ構造)**は、家系図や組織図のように、上下の関係を表すのに向いたデータ構造である。ある節から見て、直接つながっている下の節を「子」、直接つながっている上の節を「親」と呼ぶ。
とりわけよく使われるのが、各節が持てる子の数を2つまでに制限した**二分木(にぶんぎ、水準一: 各節が最大でも2つの子〈左の子・右の子〉しか持たない木構造)**である。さらに「左の子は自分より小さい値、右の子は自分より大きい値」というルールを守って値を配置したものを**二分探索木(にぶんたんさくぎ)**と呼び、この木をたどることで、配列に対する二分探索と同じような、効率のよい探索を行うことができる。
```
[8]
/ \
[3] [10]
/ \ \
[1] [6] [14]
```
この図で、8を根として、左の枝(3, 1, 6)にはすべて8より小さい値が、右の枝(10, 14)にはすべて8より大きい値が配置されている。もし6を探したければ、根の8と比較して「6は8より小さいので左へ」、次に3と比較して「6は3より大きいので右へ」、そして6にたどりつく——たった2回の比較で見つかる。データが配列のように一列に並んでいなくても、木という枝分かれの構造を使うことで、二分探索に似た効率の良い絞り込みができる、という好例である。
---
## 休憩所④: まとめ箱 — 第四章の要点
- 配列は番地でロッカーのように並ぶ入れ物。アクセスは一瞬だが、途中への挿入・削除は手間。
- 連結リストは「次の場所」を鎖状につなぐ入れ物。挿入・削除は軽いが、順にたどる必要がある。
- スタックは後入れ先出し(LIFO、重箱のお皿)、キューは先入れ先出し(FIFO、レジの行列)。
- 木構造は親子関係を枝分かれで表す。二分探索木は、探索を効率化する木の代表例。
---
## 第五章: 計算量の入口 — 「手順の良し悪し」を測る物差し
### なぜ「回数」で測るのか
第二章・第三章で見た検算(1024件の探索・整列)からわかるように、アルゴリズムの良し悪しを比べるには、「実際に何秒かかったか」ではなく、「データの件数が増えたとき、手順の回数(比較や操作の回数)がどう増えていくか」という物差しを使うのが便利である。同じアルゴリズムでも、速いコンピュータで動かせば秒数は短くなるが、「件数が2倍になったら回数が何倍になるか」という増え方の性質そのものは、コンピュータの速さに関係なく変わらないからだ。
この「件数が増えたときの手順の回数の増え方」を表す考え方を**計算量(けいさんりょう、水準一: アルゴリズムが問題を解くのに必要な手順の回数が、データの件数の増加に対してどのように増えていくかを表す指標)**と呼ぶ。
### O記法 — 「だいたいこれくらいの勢いで増える」という書き方
計算量を表すときによく使われる書き方が**O記法(オーきほう、ビッグオー記法、水準一: アルゴリズムの手順の回数が、データ件数Nに対しておおよそどんな勢いで増えていくかを、O(...)という形で表す記法)**である。細かい係数(例えば「2倍」「+3回」といった部分)を無視して、「件数が増えたときの増え方の勢いの種類」だけに注目する、という考え方だと捉えると分かりやすい。
本章までに登場したアルゴリズムを、O記法の直感で整理すると次のようになる。
```
O(1) … 件数に関係なく一定の回数で終わる(配列の番地指定アクセスなど)
O(log N) … 件数が2倍になっても回数は1回しか増えない(二分探索)
O(N) … 件数に比例して回数が増える(線形探索)
O(N log N) … 件数×「件数が2倍になっても緩やかにしか増えない量」(マージソート)
O(N^2) … 件数の2乗の勢いで回数が増える(選択ソート・挿入ソートの最悪の場合)
```
第二章の検算で見た「1024件を二分探索なら最大10回」は O(log N) の具体例であり、第三章の検算で見た「1024件の整列で単純な方法は約52万回、マージソートは約1万回」は、O(N^2) と O(N log N) という増え方の勢いの違いが、具体的な数字となって表れたものである。O記法は抽象的な記号に見えるが、その正体は「件数が増えたとき、手間がどれくらいの勢いで膨らんでいくか」という、極めて実践的な見積もりの道具なのである。
### §16.21 三つの実践解 — 紙とトランプでできる整列体験3法
アルゴリズムの理解は、紙とトランプがあれば、コンピュータなしでも体で確かめることができる。ここでは整列アルゴリズムを実際に手を動かして体験する3つの方法を、材料・工程・なぜ効くか・限界の順に紹介する。
**実践解1: トランプで選択ソートを体験する**
- 材料: トランプ(数字が読み取れれば1組で十分)
- 工程: 5〜10枚を裏向きのままバラバラに机に並べる。表向きにして、その中から一番小さい数字を探し、一番左の位置と入れ替える。残りの範囲(1枚減った範囲)でまた最小値を探して入れ替える、を繰り返す。
- なぜ効くか: 「未整列部分から最小を探して確定させる」という選択ソートの動きを、体の動作として体験できる。何回見比べたかを指折り数えれば、件数と比較回数の関係を肌で感じられる。
- 限界: 枚数が20枚を超えると、目視での最小値探しにミスが出やすく、体験の正確さが落ちる。少人数(5〜10枚)での実施が向いている。
**実践解2: トランプで挿入ソートを体験する**
- 材料: トランプ
- 工程: 山札から1枚ずつ引き、すでに手札にある整列済みのカードの正しい位置に差し込んでいく(実際のトランプゲームで手札を並べる動作そのもの)。
- なぜ効くか: 挿入ソートの「整列済み部分に差し込む」という動きは、多くの人がゲームで無意識にやっている動作と一致するため、アルゴリズムという抽象的な概念が「すでに知っている動作」であったことに気づける。
- 限界: 手札が多くなると差し込む位置を探す手間が増えるため、O(N^2)的な増え方を体感するには向くが、大人数での一斉体験には不向き(1人1組のトランプが必要)。
**実践解3: 紙に書いた数字でマージソートを体験する**
- 材料: 数字を書いた紙片8枚程度、または8マスの表を書いた紙1枚
- 工程: 8個の数字を半分(4個ずつ)に分け、さらに半分(2個ずつ)に分け、さらに半分(1個ずつ)に分ける。1個ずつになったら、隣同士を比較しながら2個の整列済みの組を作り、それを2つ統合して4個の組を作り、最後に2つの4個の組を統合して8個の整列済みの列を完成させる。
- なぜ効くか: 「分割してから統合する」という再帰の考え方は、頭の中だけで理解しようとすると抽象的になりがちだが、実際に紙を並べて分割・統合の様子を目で追うことで、「小さな問題に分けてから組み合わせる」という発想の流れを具体的に追体験できる。
- 限界: 数字が少ない(8個程度)うちは効率の良さが実感しにくく、「わざわざ分割する意味があるのか」と感じられてしまう。件数が多いほど有利になる、という性質は、実物の紙の枚数を増やしにくいため体感しづらい限界がある。
---
## 章末: 手順という発明の階段
この冊子で歩いた「アルゴリズムとデータ構造」の道のりを、階段図としてまとめておく。
```
[水準四] 計算量という物差し
O(1) < O(log N) < O(N) < O(N log N) < O(N^2)
「件数が増えたときの増え方の勢い」を測る
▲
│ 入れ物そのものを工夫する
[水準三] データ構造
配列・連結リスト・スタック・キュー・木構造
▲
│ データを賢く並べ替える
[水準二] 整列アルゴリズム
選択ソート・挿入ソート・マージソート(分割統治)・クイックソート(1960年ごろ)
▲
│ データを賢く探す
[水準二] 探索アルゴリズム
線形探索・二分探索(2^10=1024件を最大10回)
▲
│ 「有限の明確な手順」という発想そのもの
[水準一] アルゴリズムの起源
ユークリッドの互除法(紀元前300年ごろ)
アル=フワーリズミー(9世紀、語源・諸説あり)
エイダ・ラヴレス(1843年、解析機関のノート)
```
そろばんが「記憶する道具」、パンチカードが「手順を穴の模様で記録する道具」だったように(→BOOK-0010『コンピュータの始まり』第1冊参照)、アルゴリズムとデータ構造は「手順そのものと、データの置き場所そのものを、いかに賢く設計するか」という、コンピュータの中身に関わる、もう一段深い階段である。→BOOK-0002『算術』第1冊で見た位取り記数法が「数をどう書き表すか」の工夫であったように、この冊子で見たアルゴリズムは「数や情報をどう扱う手順を書き表すか」の工夫であり、両者は「表現を工夫することで、扱いやすさが劇的に変わる」という同じ精神でつながっている。
次の巻では、この計算量という物差しをさらに掘り下げ、O記法の厳密な定義や、探索木の平衡化、グラフというより複雑なデータ構造、そして「解くのに現実的な時間がかかるかどうか」という計算の難しさそのものを測る領域へと歩を進めていく。手順という発明の階段は、ここからさらに高く続いている。
# BOOK-0066 アルゴリズムとデータ構造 — 「手順」という発明の階段(第1巻)