🗺️ このノートは 第6章「計算量とデータ構造の基礎」のハブ です。
第6章 ── 計算量とデータ構造の基礎
ここまでハード（第1章）とOS（第2〜5章）を見てきました。最後に、その上で動くプログラム自体の効率を測る言語を持ちます。「nが大きくなると、どれくらい遅くなるか」を表すオーダー記法、データの持ち方で操作コストが変わるデータ構造、そして探索と整列の古典です。
ここは実装基盤の視点に絞ります。計算量の理論的な深掘り（NP困難・帰着・下界証明）は 数理最適化／機械学習 へ繋ぎ、本章は「どのデータ構造・アルゴリズムを選ぶと実際に速いか」という実践的な土台に徹します。
トピック一覧
- 計算量とオーダー記法 — O記法・時間/空間計算量・増え方の比較
- 基本データ構造 — 配列・連結リスト・木・ハッシュの操作コスト
- 基本アルゴリズム — 線形/二分探索・整列のトレードオフ
この章の位置づけ
- 計算量はCPU性能式（性能の評価とアムダールの法則）の「命令数(IC)」の源。アルゴリズム改善はICを減らす
- 実速度は計算量だけでなく局所性（メモリ階層とキャッシュ）にも左右される
- 理論の深掘り（NP困難・近似）は 数理最適化／機械学習 へ