アルゴリズムとデータ構造

情報科学学部無料 3 章有料 4 章

計算量（O記法）の概念をまず厳密に説明し、それがなぜ重要か（入力サイズに対するスケーラビリティ）を強調する。

想定読者: 大学生（情報系）・社会人エンジニア

目次

1. 第 1 章計算量とO記法無料時間計算量・空間計算量を計算モデルから定義し、O・Ω・Θ 記法を関数の集合として厳密に述べる。増大度の階層を証明し、O(1) から O(2^n) までの各クラスが入力サイズの増大にどう耐えるかを定理と数値で比較する。
2. 第 2 章基本的なデータ構造無料配列と連結リストのメモリ配置の違いから検索・挿入・削除の計算量を導き、動的配列の償却 O(1) を証明する。スタックとキューを抽象データ型として定義し、リングバッファと 2 本のスタックによる実装を解析する。
3. 第 3 章ソートアルゴリズム無料バブルソートが二乗時間になる理由を転倒数で説明し、マージソートの分割統治が n log n を達成することを証明する。クイックソートの平均計算量と最悪計算量の差がピボットの選び方から生じる仕組みまで扱う。
4. 第 4 章探索アルゴリズム本ソート済み配列に対する二分探索が O(log n) で終わる理由を不変条件と決定木の下界から示し、ハッシュ表がチェイン法とオープンアドレス法で平均 O(1) を実現する仕組みと、その「平均」の中身を明らかにする。
5. 第 5 章グラフアルゴリズム本グラフを隣接行列と隣接リストで表し、幅優先探索が最短の辺数を与えること、深さ優先探索が有向閉路を検出することを証明する。さらに非負重みの下でダイクストラ法の正当性を示し、優先度付きキューによる O(E log V) を導く。
6. 第 6 章動的計画法（Dynamic Programming）本動的計画法を「部分問題の依存関係が DAG なら位相順に一度ずつ解けばよい」という原理として定式化し、フィボナッチ数列の指数時間再帰が O(n) になる仕組みと、0-1 ナップサック問題の漸化式・O(nW) 表計算・解の復元を証明付きで示す。
7. 第 7 章P≠NP予想とは何か本クラス P と NP を検証器の言葉で厳密に定義し、多項式時間帰着と NP 完全性から SAT・3SAT・独立集合の関係を証明する。P=NP なら暗号と最適化に何が起きるかまで具体的に示す。

「アルゴリズムとデータ構造」は 1 冊の本としてまとめています。無料章を読んで続きが気になったら、本の一覧からどうぞ。