※小説ではない※専門書 要約資料集 為替(換算)3.9万円でもらう 紐解集生成 専門 初入門 資料 作：｛作者名｝
> 学問の宇宙・史料図書(§16.17)第207号。図解・一覧が主役の簡易専門書。ガイド役: Fable 5 監修 / Sonnet 5 執筆(史料図書隊・情報担当)。
> 位置づけ: BOOK-0066『アルゴリズムとデータ構造 — 「手順」という発明の階段(第1巻)』は歴史の物語(散文)を担当する。本冊はそれと**重複せず**、計算量・ソート・探索・データ構造そのものを**一望できる早見表・計算量とデータ構造の一覧**として機能する。
> 文章規約: 見出し+一行解説主体。専門語は初出に水準(§14.2)を付す。外部本文の転載はしない(§16.5)。数値は確実なものだけを断言し、それ以外は「約」「概数」と明記する。
# BOOK-0207 情報史料 — アルゴリズムとデータ構造の早見
> 学問の宇宙・史料図書(§16.17)第207号。図解・一覧が主役の簡易専門書。ガイド役: Fable 5 監修 / Sonnet 5 執筆(史料図書隊・情報担当)。
> 位置づけ: BOOK-0066『アルゴリズムとデータ構造 — 「手順」という発明の階段(第1巻)』は歴史の物語(散文)を担当する。本冊はそれと**重複せず**、計算量・ソート・探索・データ構造そのものを**一望できる早見表・計算量とデータ構造の一覧**として機能する。
> 文章規約: 見出し+一行解説主体。専門語は初出に水準(§14.2)を付す。外部本文の転載はしない(§16.5)。数値は確実なものだけを断言し、それ以外は「約」「概数」と明記する。
---
## 目次
1. 計算量O記法の早見(速さ順)
2. 主要ソートの比較表
3. 探索の早見(線形探索・二分探索)
4. データ構造の早見(得意操作と計算量)
5. 再帰と反復の一行まとめ
6. ASCII図解(木・連結リスト・スタック)
7. 擬似コード集
8. 数値検算ログ(実測・自己検算)
9. 検定問題(public/answers)
---
## 1. 計算量O記法の早見(速さ順)
**計算量(けいさんりょう、水準一: アルゴリズムが問題を解くのに必要な手順の回数が、データ件数Nの増加に対してどう増えていくかを表す指標)**を、**O記法(オーきほう、ビッグオー記法、水準一: 手順の回数がデータ件数Nに対しどんな勢いで増えるかを O(...) の形で表す記法)**で、速い順に並べる。
| O記法 | 読み方 | 増え方の一行解説 | 水準 |
|---|---|---|---|
| `O(1)` | オーいち(定数時間) | 件数Nに関係なく、常に一定の手順回数で終わる。 | 一 |
| `O(log n)` | オーログエヌ(対数時間) | 件数が2倍になっても、手順回数はたった1回しか増えない。 | 二 |
| `O(n)` | オーエヌ(線形時間) | 件数に比例して、手順回数もそのまま増える。 | 一 |
| `O(n log n)` | オーエヌログエヌ(線形対数時間) | 件数×「緩やかにしか増えない量」。優秀な整列法の代表的な勢い。 | 三 |
| `O(n²)` | オーエヌにじょう(二乗時間) | 件数の2乗の勢いで手順回数が膨らむ。 | 二 |
| `O(2^n)` | オーにのえぬじょう(指数時間) | 件数が1増えるごとに手順回数が2倍になる、極めて重い増え方。 | 四 |
```
速さの順序(左ほど速い・水準一〜四のまとめ)
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n)
```
- `O(1)`の例: 配列の「何番目か」を指定してのアクセス(番地が分かれば一瞬)。
- `O(log n)`の例: 整列済みデータへの二分探索。
- `O(n)`の例: 先頭から順に確認する線形探索。
- `O(n log n)`の例: マージソート・ヒープソート・クイックソート(平均)。
- `O(n²)`の例: バブルソート・選択ソート・挿入ソート(いずれも最悪計算量)。
- `O(2^n)`の例: すべての組み合わせを網羅的に試す一部の探索(件数が増えると現実的な時間で終わらなくなる代表格)。
---
## 2. 主要ソートの比較表
**整列アルゴリズム(せいれつアルゴリズム、水準一: バラバラな順序のデータを決まった順序に並べ替える手順)**、いわゆる「ソート」を計算量で比較する。
| ソート名 | 平均計算量 | 最悪計算量 | 水準 | 一行解説 |
|---|---|---|---|---|
| バブルソート | O(n²) | O(n²) | 一 | 隣り合う2つを比較し、順序が逆なら入れ替える動作を端から端まで繰り返す。 |
| 選択ソート | O(n²) | O(n²) | 一 | 未整列部分から最小値を探し、未整列部分の先頭と入れ替える動作を繰り返す。 |
| 挿入ソート | O(n²) | O(n²) | 一 | 整列済み部分に、未整列の要素を一つずつ正しい位置へ挿入していく。 |
| マージソート | O(n log n) | O(n log n) | 三 | データを半分ずつに分割し、それぞれ整列してから統合(マージ)する分割統治法。 |
| ヒープソート | O(n log n) | O(n log n) | 三 | ヒープ(木構造の一種)を作り、最大〈最小〉値を1つずつ取り出して並べる。 |
| クイックソート | O(n log n) | O(n²) | 三 | 基準値(ピボット)より小さい/大きいで振り分けてから、それぞれを再帰的に整列する。 |
```
比較表の一行早見(速さの傾向)
バブル・選択・挿入 → O(n²) … 件数が増えるほど急激に重くなる
マージ・ヒープ → O(n log n) … 最悪の場合でも安定して速い
クイック → O(n log n)(平均)だが最悪 O(n²) … 基準値の選び方次第で最悪ケースあり
```
- バブル・選択・挿入の3つは実装が単純で理解しやすい反面、件数が数千〜数万に増えると`O(n²)`の重さが顕著になる。
- マージソート・ヒープソートは最悪の場合でも`O(n log n)`を保証する安定した速さを持つ。
- クイックソートは平均では最も高速な部類だが、基準値の選び方が悪いと最悪`O(n²)`まで落ち込む場合がある、という点が実務上の注意点である。
---
## 3. 探索の早見(線形探索・二分探索)
| 探索法 | 計算量 | 前提条件 | 水準 | 一行解説 |
|---|---|---|---|---|
| 線形探索 | O(n) | なし(整列不要) | 一 | 先頭から順に一つずつ確認していく、最も素直な探索方法。 |
| 二分探索 | O(log n) | データが整列済みであること | 二 | 真ん中の要素と比較し、探索範囲を半分ずつに絞り込んでいく。 |
```
探索法の使い分け(一行早見)
整列されていないデータ・一度きりの探索 → 線形探索 O(n)
整列済みデータ・繰り返し何度も探す → 二分探索 O(log n)
```
- 二分探索は「データが整列済み」という前提が崩れると使えない。整列そのものにもコスト(§2参照)がかかるため、「何度も探すなら先に整列して二分探索、一度きりなら線形探索」という判断が実務上の目安になる。
---
## 4. データ構造の早見(得意操作と計算量)
**データ構造(データこうぞう、水準一: データを効率よく扱えるように整理して収める、記憶上の入れ物の設計)**ごとに、得意な操作と代表的な計算量を一覧化する。
| データ構造 | 得意な操作 | 代表的な計算量 | 水準 | 一行解説 |
|---|---|---|---|---|
| 配列 | 番地(インデックス)指定でのアクセス | アクセス O(1) / 途中への挿入・削除 O(n) | 一 | 番号のついたロッカーが横一列に並ぶイメージ。番地さえ分かれば一瞬でアクセスできる。 |
| 連結リスト | 途中への挿入・削除 | 挿入・削除 O(1)(位置が分かっている場合) / 先頭からの探索 O(n) | 二 | 各データが「次の場所」を示す情報を持ち、鎖のようにつながる。 |
| スタック | 末尾への追加・末尾からの取り出し(LIFO・後入れ先出し) | 追加・取り出し O(1) | 一 | 重箱にお皿を積むように、最後に入れたものを最初に取り出す。 |
| キュー | 末尾への追加・先頭からの取り出し(FIFO・先入れ先出し) | 追加・取り出し O(1) | 一 | スーパーのレジ待ちの行列のように、先に入れたものを先に取り出す。 |
| 木(二分探索木) | 整列された状態での探索・挿入・削除 | 平均 O(log n) / 最悪 O(n)(偏った木の場合) | 三 | 根から枝分かれし、親子関係でつながる。左の子は小さい値、右の子は大きい値というルールを持つものが二分探索木。 |
| ハッシュ表 | キーを指定してのデータの検索・追加・削除 | 平均 O(1) / 最悪 O(n)(衝突が多い場合) | 三 | キーをハッシュ関数で変換し、対応する場所に直接データを格納・参照する。 |
| グラフ | 要素間の関係(つながり)の表現・探索 | 探索の計算量は表現方法・アルゴリズムに依存(例: 幅優先探索は O(頂点数+辺数)) | 四 | 点(頂点)と点同士をつなぐ線(辺)で、ネットワークのような関係性を表す。 |
```
得意操作の一行早見(まとめ)
配列 → 番地アクセスが得意(O(1))・途中挿入は苦手(O(n))
連結リスト → 途中挿入・削除が得意・順番のたどりは苦手(O(n))
スタック → 後入れ先出し(LIFO)専用の出し入れがO(1)
キュー → 先入れ先出し(FIFO)専用の出し入れがO(1)
木 → 親子関係の表現・整列された探索が得意(平均O(log n))
ハッシュ表 → キー指定での検索が得意(平均O(1))
グラフ → 「つながり」そのものの表現に特化
```
- 配列と連結リスト、スタックとキューは、それぞれ「得意・不得意が裏返しの関係」になっている代表的な対比である。
- 木構造は「偏りなく枝分かれしている」場合に`O(log n)`が成立する。片方にだけ伸び続けた偏った木は、最悪`O(n)`まで悪化する(実質的に連結リストと同じ形になるため)。
- ハッシュ表の`O(1)`も「衝突(異なるキーが同じ場所に割り当てられること)が少ない」という前提つきの平均計算量である。
---
## 5. 再帰と反復の一行まとめ
| 考え方 | 一行解説 | 水準 |
|---|---|---|
| 反復(はんぷく、iteration) | 同じ処理を、ループ(繰り返し構文)を使って何度も実行する考え方。 | 一 |
| 再帰(さいき、recursion) | ある手順の中で、その手順自身をより小さな問題に対して呼び出す考え方。 | 二 |
- 反復はループ(for・whileなど)で「同じことを繰り返す」動きを直接書く。
- 再帰は「大きな問題を、同じ形をした小さな問題に分割し、小さな問題を解いてから組み合わせる」という戦略で、マージソート・クイックソート・木構造の探索などで頻繁に使われる(BOOK-0066第三章参照)。
- 同じ処理を再帰でも反復でも書ける場合が多いが、再帰は「分割統治」のような自己相似な問題との相性が良く、反復は単純な繰り返し処理との相性が良い、という使い分けの目安がある。
---
## 6. ASCII図解(木・連結リスト・スタック)
### 6.1 木構造(二分探索木の例)
```
[8]
/ \
[3] [10]
/ \ \
[1] [6] [14]
読み方: 8が根(ルート)。左の枝(3,1,6)は8より小さい値、
右の枝(10,14)は8より大きい値というルールで並ぶ。
6を探す場合: 8と比較→6は小さいので左へ→3と比較→6は大きいので右へ→発見(2回の比較)。
```
### 6.2 連結リスト
```
[先頭] → [データA|次へ] → [データB|次へ] → [データC|次へ] → NULL(終端)
読み方: 各要素が「次の要素の場所」だけを持ち、鎖のようにつながる。
途中(例: AとBの間)に新しい要素を挿入するときは、
「次へ」の矢印を1本つなぎ替えるだけで済み、他の要素はずらさなくてよい。
```
### 6.3 スタック(LIFO・後入れ先出し)
```
push(積む)方向
↓
┌────┐
│ C │ ← 最後に積んだものが一番上(=最初に取り出される)
├────┤
│ B │
├────┤
│ A │ ← 最初に積んだものが一番下
└────┘
↑
pop(取り出す)は必ず一番上(C)から
```
---
## 7. 擬似コード集
### 7.1 二分探索
```
手順(二分探索):
1. 探索範囲全体の「真ん中」の要素を見る
2. 探している値と一致すれば、見つかったので終了
3. 探している値が真ん中より小さいなら、範囲を前半だけに絞る
4. 探している値が真ん中より大きいなら、範囲を後半だけに絞る
5. 絞り込んだ範囲に対して手順1へ戻る(範囲が空なら「存在しない」と判定)
```
### 7.2 マージソート(分割統治・再帰の例)
```
手順(マージソート):
1. データが1個以下なら、すでに整列済みとみなして終了
2. データを前半と後半、ほぼ半分ずつに分割する
3. 前半に対して、この手順(1〜4)を再び適用する(再帰)
4. 後半に対しても同様にこの手順を再び適用する(再帰)
5. 整列された前半と後半を、先頭同士を比べながら1つの列に統合(マージ)する
```
### 7.3 スタックを使った操作の基本形
```
手順(スタックの基本操作):
push(値): スタックの一番上に値を積む
pop(): スタックの一番上から値を取り出して取り除く
peek(): スタックの一番上の値を、取り除かずに確認する
```
---
## 8. 数値検算ログ(実測・自己検算)
自己検算を実施し、結果のみ断言する。
1. **log2(1024)=10 の検算**: 2を10回掛け合わせると `2^10 = 1024`。よって`log2(1024)=10`(検算一致)。二分探索なら1024件のデータを最大10回の比較で絞り込める。
2. **選択ソート(O(n²))の概算比較回数**: N=1024のとき、未整列部分から最小値を探す比較の合計はおよそ`N×(N-1)÷2`回。計算すると`1024×1023÷2=523776`回(概数「約52万回」)。
3. **マージソート(O(n log n))の概算比較回数**: N=1024のとき、`N×log2(N)=1024×10=10240`回(概数「約1万回」)。
4. **選択ソートとマージソートの比較回数の比**: `523776÷10240 ≈ 51.15`。よって約51倍、選択ソートの方が比較回数が多い(概数「約50倍」)。
5. **O(2^n)の急増の検算**: nが10のとき`2^10=1024`、nが20のとき`2^20=1048576`。nがわずか10増えただけで、回数はおよそ1024倍に増える(`1048576÷1024=1024`、検算一致)。
---
## 9. 検定問題
### quiz_public(鍵なし・配布用)
以下12問。各問四択。答えの記載はなし(読者検定用)。
1. (易) `O(1)`の一行解説として正しいものはどれか。 A.件数に比例して回数が増える B.件数に関係なく一定の回数で終わる C.件数の2乗の勢いで回数が増える D.件数が2倍になると回数も2倍になる
2. (易) 二分探索の計算量として正しいものはどれか。 A.O(1) B.O(n) C.O(log n) D.O(n²)
3. (易) バブルソート・選択ソート・挿入ソートに共通する計算量はどれか。 A.O(log n) B.O(n) C.O(n log n) D.O(n²)
4. (易) スタックのルール(LIFO)の一行解説として正しいものはどれか。 A.先に入れたものを先に取り出す B.最後に入れたものを最初に取り出す C.真ん中の要素から取り出す D.ランダムな順に取り出す
5. (中) マージソート・ヒープソート・クイックソートに共通する平均計算量はどれか。 A.O(n) B.O(n²) C.O(n log n) D.O(2^n)
6. (中) 二分探索を使うための前提条件として正しいものはどれか。 A.データが整列済みであること B.データが未整列であること C.データが木構造であること D.データがハッシュ表であること
7. (中) 配列の弱点として本文が挙げているものはどれか。 A.番地アクセスが遅い B.途中への挿入・削除に手間がかかる C.順番にしかアクセスできない D.整列ができない
8. (中) キュー(FIFO)の身近な例として本文が挙げているものはどれか。 A.重箱にお皿を積む動作 B.スーパーのレジ待ちの行列 C.本棚から本を探す動作 D.木の枝分かれ
9. (難) log2(1024)の検算結果として正しいものはどれか。 A.8 B.9 C.10 D.11
10. (難) N=1024のとき、選択ソートの概算比較回数として本文が示す値はどれか。 A.約1万回 B.約5万回 C.約52万回 D.約100万回
11. (難) 二分探索木が最悪O(n)まで悪化する条件として本文が説明するものはどれか。 A.枝分かれが均等な場合 B.片方にだけ偏って伸び続けた場合 C.データが整列されている場合 D.ハッシュ関数を使った場合
12. (難) ハッシュ表の平均計算量O(1)が成立する前提として本文が説明するものはどれか。 A.衝突が少ないこと B.データが整列済みであること C.木構造であること D.再帰を使っていること
### answers(鍵・根拠つき・非公開)
| 問 | 正解 | 根拠(本文箇所) |
|---|---|---|
| 1 | B | §1計算量O記法の早見の表: 「件数Nに関係なく、常に一定の手順回数で終わる」(O(1)の行) |
| 2 | C | §3探索の早見の表: 「二分探索 O(log n)」 |
| 3 | D | §2主要ソートの比較表: 「バブル・選択・挿入の3つは実装が単純で理解しやすい反面」の段落、および表の該当3行がいずれもO(n²) |
| 4 | B | §6.3スタック図解: 「最後に積んだものが一番上(=最初に取り出される)」 |
| 5 | C | §2主要ソートの比較表: マージソート・ヒープソート・クイックソートの表内、平均計算量の列がいずれもO(n log n) |
| 6 | A | §3探索の早見の表: 二分探索の行、前提条件の列に「データが整列済みであること」 |
| 7 | B | §4データ構造の早見の表: 「配列 … 途中への挿入・削除 O(n)」、一行解説「番地さえ分かれば一瞬でアクセスできる」の対比記述 |
| 8 | B | §4データ構造の早見の表: 「スーパーのレジ待ちの行列のように、先に入れたものを先に取り出す」(キューの行) |
| 9 | C | §8数値検算ログ1: 「2を10回掛け合わせると `2^10 = 1024`。よって`log2(1024)=10`」 |
| 10 | C | §8数値検算ログ2: 「`1024×1023÷2=523776`回(概数「約52万回」)」 |
| 11 | B | §4データ構造の早見の補足: 「片方にだけ伸び続けた偏った木は、最悪`O(n)`まで悪化する」 |
| 12 | A | §4データ構造の早見の補足: 「ハッシュ表の`O(1)`も「衝突(異なるキーが同じ場所に割り当てられること)が少ない」という前提つきの平均計算量である」 |
**分散チェック(outputs/node_test_book0207.jsで実測)**: 正解インデックス内訳 = A:2問(#6,#12)、B:5問(#1,#4,#7,#8,#11)、C:4問(#2,#5,#9,#10)、D:1問(#3)。4種のインデックスを全て使用し、最大出現数は5問(B)で上限6問以内、最低3種以上の規定(§16.4)を満たす(2026-07-04実測・機械検査PASS)。
---
## 図解総まとめ
```
史料図書BOOK-0207の九枚看板
① 計算量O記法の早見(O(1)〜O(2^n)を速さ順に)
② 主要ソートの比較表(バブル/選択/挿入=O(n²)、マージ/ヒープ/クイック=O(n log n)平均)
③ 探索の早見(線形O(n)・二分探索O(log n))
④ データ構造の早見(配列・連結リスト・スタック・キュー・木・ハッシュ表・グラフ)
⑤ 再帰と反復の一行まとめ
⑥ ASCII図解(木・連結リスト・スタック)
⑦ 擬似コード集(二分探索・マージソート・スタック操作)
⑧ 数値検算ログ(log2(1024)=10等の自己検算)
⑨ 検定問題(quiz_public+answers 12問・易4中4難4)
```
## 参照文献
1. BOOK-0066『アルゴリズムとデータ構造 — 「手順」という発明の階段(第1巻)』(本図書館・散文版・アルゴリズムの歴史とデータ構造の物語を扱う)。
2. 標準的な計算機科学の教科書水準で広く共有されている、ソート・探索アルゴリズムの計算量分類(バブル/選択/挿入=O(n²)、マージ/ヒープ=O(n log n)、クイック=平均O(n log n)・最悪O(n²))。
3. 標準的なデータ構造(配列・連結リスト・スタック・キュー・木・ハッシュ表・グラフ)の定義と代表的な計算量。
# BOOK-0207 情報史料 — アルゴリズムとデータ構造の早見