 |
このサポートページでは、マイナビ出版発行の書籍「アルゴリズムビジュアル大事典」にて作成しましたシンボル、アニメーション、疑似コードを掲載いたします。また、内容のアップデートを行ってまいります。詳しい解説は、本書をご参考にしてください。
アニメーションコントローラの使い方はクイックマニュアルでご確認頂けます。
補足情報が表示されているトピックにつきましては、ご注意ください。その他の訂正等は正誤表をご覧ください。ご質問、不具合等のご報告は、ご遠慮なくy.watanobe@gmail.com（渡部）までお送りください。
Part 1 準備編
3章 計算量
|
|
|
Part 2 空間構造
4-9章
Part 3 アルゴリズムとデータ構造
10章 入門
2021/05/10
2021/05/10
2021/05/10
11章 配列に対する基本クエリ
2021/05/10
2021/05/10
2021/05/10
12章 探索
2021/05/10
2021/05/10
13章 配列要素の並び替え
2021/05/10
2021/05/10
2021/05/10
2021/05/10
14章 遅いソート
2021/05/10
2021/05/10
2021/05/10
※このアルゴリズムは、本書に含まれません。2021/05/11
15章 整数に関するアルゴリズム
2021/05/11
2021/05/11
16章 基本データ構造1
2021/05/23
2021/05/23
17章 配列に対する計算
2021/05/16
2021/05/16
2021/05/22
※このアルゴリズムは、本書に含まれません。2021/05/22
18章 ヒープ
2021/05/22
2021/05/22
2021/05/22
2021/05/23
基本データ構造：比較表
| データ構造 | 計算量 | ルール | テクニック | |
|---|---|---|---|---|
|
スタック |
|
後入先出 (LIFO: Last-In-First-Out) | |
|
キュー |
|
先入先出 (FIFO: First-In-First-Out) | |
|
優先度付きキュー |
|
優先度の高いものから取り出す |
|
19章 二分木
2021/05/30
2021/05/30
2021/05/30
2021/05/30
20章 ソート
2021/05/15
2021/05/15
2021/05/22
2021/05/15
2021/05/15
ソートアルゴリズム：比較表
| アルゴリズム | 計算量 | 安定性 | インプレイス （メモリ効率） |
テクニック | 特徴 | |||
|---|---|---|---|---|---|---|---|---|
|
バブルソート |
|
〇 | 〇 |
|
× 実用的ではない | ||
|
選択ソート |
|
× | 〇 |
|
× 実用的ではない | ||
|
挿入ソート |
|
〇 | 〇 |
|
〇昇順に近いデータに対して高速 | ||
|
シェーカーソート |
|
〇 | 〇 |
|
〇昇順に近いデータに対して高速 | ||
|
マージソート |
|
〇 | × |
|
〇 安定でかつ高速 × メモリが必要 |
||
|
クイックソート |
|
× | 〇 |
|
× 基準の選び方で遅くなる 〇 インプレイスで高速 |
||
|
ヒープソート |
|
× | 〇 |
|
× システムによって実行速度が遅くなる可能性がある | ||
|
シェルソート |
|
× | 〇 |
|
× 間隔の選び方によって遅くなる | ||
|
計数ソート |
|
〇 | × |
|
× 要素の値に上限がある | ||
21章 基本データ構造2
2020/05/17
2020/05/17
22章 幅優先探索
2020/05/17
2020/05/17
2020/05/17
23章 深さ優先探索
2020/05/17
2020/05/17
2020/05/17
2020/05/17
24章 Union-Find 木
2020/04/19
2020/04/19
2020/04/19
25章 最小全域木を求めるアルゴリズム
2020/05/17
2020/05/17
26章 最短経路を求めるアルゴリズム
2020/05/17
2020/05/17
2020/05/17
2020/05/17
最短経路のアルゴリズム：比較表
| アルゴリズム | 計算量 | 距離 | テクニック | |
|---|---|---|---|---|
|
幅優先探索 |
|
単一始点から全てのノードへの最短経路（エッジ数） |
|
|
ダイクストラのアルゴリズム （線形探索） |
|
単一始点から全てのノードへの最短経路 ※負の重みがあってはならない |
|
|
ダイクストラのアルゴリズム |
|
単一始点から全てのノードへの最短経路 ※負の重みがあってはならない |
|
|
ベルマンフォードのアルゴリズム |
|
単一始点から全てのノードへの最短経路 負の重みがあってもよい 負のサイクルを検出可能 |
|
|
ワーシャルフロイドのアルゴリズム |
|
全点対間の最短経路 負の重みがあってもよい 負のサイクルを検出可能 |
|
27章 計算幾何学
2020/05/17
2020/05/17
2020/05/17
28章 セグメント木
2020/05/17
2020/05/17
29章 探索木
2020/05/17
2020/05/17
2020/05/17
辞書のデータ構造：比較表
| データ構造 | 計算量 | メモリ効率 | 順序付き | 応用 | |
|---|---|---|---|---|---|
|
連結リスト |
|
〇 | 〇順序付き | リスト、辞書 |
|
ハッシュ表 |
|
× | × | 辞書 |
|
二分探索木 |
|
〇 | 〇整列済み | 辞書、集合、 優先度付きキュー、最大・最小 |
|
トリープ |
|
〇 | 〇整列済み | 辞書、集合、 優先度付きキュー、最大・最小 |
本書に掲載できなかったアルゴリズム
- シェーカーソート(2020/05/13)
- グリッド上の動的計画法(2020/06/07)