はじめに
アルゴリズムとデータ構造の全体像を学習する備忘録です。
改訂履歴
- 2026/10/02 : 初版公開。
本文
1. アルゴリズム
アルゴリズム (Algorithm) とは、ある問題を解決するための具体的な手順です。より形式的には、意味が明確で、有限時間内に実行できる有限個の手順によって、問題を解決する方法と説明されます。
例えば「配列の中から目的の値を探す」という問題を考えた場合、以下の手順を考えることができます。
- 配列の先頭を見る
- 目的の値と比較する
- 一致していれば終了する
- 一致していなければ次の要素を見る
- 最後まで繰り返す
この手順は、線形探索 (Linear Search) というアルゴリズムになります。
1-1. 計算量
計算量とは、アルゴリズムの効率を表す指標です。入力データの大きさに対して、アルゴリズムがどの程度の時間やメモリを必要とするのかを表します。計算量には、主に以下の 2 種類があります。
- 時間計算量 : アルゴリズムの実行に必要な時間を表す
- 空間計算量 : アルゴリズムの実行に必要なメモリ量を表す
例えば 100 個のデータを処理する場合と 10,000 個のデータを処理する場合では、アルゴリズムによって必要な時間やメモリ量の増え方が異なります。この「入力サイズが大きくなったときに、計算量がどのように増加するか」を表すために、ビッグ・オー (Big-O) 記法が使われます。代表的なものとして、以下があります。
| 記法 | 名称 | 特徴 |
|---|---|---|
O(1) |
定数時間 | 入力サイズに依存しない |
O(log n) |
対数時間 | 入力が増えても増加が小さい |
O(n) |
線形時間 | 入力サイズに比例して増加する |
O(n log n) |
線形対数時間 | 効率的なソートなどで登場する |
O(n²) |
二次時間 | 入力サイズの 2 乗に比例して増加する |
2. データ構造
データ構造 (Data Structure) とは、データを効率よく保持したり操作したりするための方法や形式のことを指します。
代表的なデータ構造には以下のものがあります。
① 線形データ構造
- 配列 : データを順番に並べて管理する
- リスト : データをつなげて管理する
- スタック : 後から入れたデータを先に取り出す (LIFO / Last In First Out)
- キュー（待ち行列） : 先に入れたデータを先に取り出す (FIFO / First In First Out)
② 非線形データ構造
- 木構造（ツリー構造） : データを階層構造で管理する
- グラフ : データ同士のつながりを表現する
③ その他のデータ構造
- ハッシュテーブル : キーを使ってデータを効率よく検索する
アルゴリズムとデータ構造は密接に関係しています。例えば、同じ「データを探す」という処理でも、単純な配列を使う場合とハッシュテーブルを使う場合では、必要となるアルゴリズムや計算量が異なります。
3. アルゴリズムの種類
アルゴリズムには様々な種類があります。まずはデータ構造や問題の種類に応じて、代表的なアルゴリズムをざっくりと分類して整理します。
3-1. 探索アルゴリズム
データの中から、目的のデータを探すためのアルゴリズムです。計算量に登場する V は頂点数、E は辺数を表します。
| アルゴリズム | 概要 | 計算量 |
|---|---|---|
| 線形探索 | データを先頭から順番に調べる。 | O(n) |
| 二分探索 | データを半分ずつ絞り込みながら探す。 | O(log n) |
| ハッシュ探索 | ハッシュ値を利用してデータを探す。 | 平均 O(1) となる。 |
| 深さ優先探索 (DFS) | グラフや木を深く探索する。 | O(V + E) |
| 幅優先探索 (BFS) | グラフや木を横方向に探索する。 | O(V + E) |
3-2. ソートアルゴリズム
データを指定した順序に並べ替えるためのアルゴリズムです。
| アルゴリズム | 概要 | 平均計算量 | 最悪計算量 |
|---|---|---|---|
| バブルソート（基本交換法） | 隣り合うデータを比較して交換する。 | O(n²) |
O(n²) |
| 選択ソート（基本選択法） | 最小値や最大値を選択して並べる。 | O(n²) |
O(n²) |
| 挿入ソート（基本挿入法） | データを適切な位置に挿入して並べる。 | O(n²) |
O(n²) |
| シェルソート | 一定間隔を空けて比較・交換しながら並べる。 | 実装による。 | 実装による。 |
| マージソート | データを分割して、それぞれをソートして統合する。 | O(n log n) |
O(n log n) |
| クイックソート | 基準値を使ってデータを分割しながらソートする。 | O(n log n) |
O(n²) |
| ヒープソート | データをヒープという木構造に整理し、最大値や最小値を順番に取り出して並べる。 | O(n log n) |
O(n log n) |
3-3. 再帰アルゴリズム
ある処理の中から、同じ処理自身を呼び出すアルゴリズムです。再帰を理解することで、木構造や分割統治法などのアルゴリズムを理解しやすくなります。前項のクイックソートやマージソートも、再帰を用いて表す代表的なアルゴリズムです。
| 例 | 概要 | 計算量 |
|---|---|---|
| 階乗計算 |
n! = n × (n - 1)! のように、同じ計算を繰り返す。 |
O(n) |
| フィボナッチ数列 | 前の 2 つの値を使って次の値を求める。 | 実装による。 |
| 木構造の探索 | 子ノードに対して同じ探索処理を繰り返す。 | 全ノードを探索する場合は O(n) となる。 |
大きな問題を小さな問題に分割し、それぞれを解決してから結果を統合する手法を分割統治法と呼びます。分割統治法では、再帰を使って実装することが多く、マージソートやクイックソートなどが代表的な例です。
おわりに
CS の花形分野だけあって、調べれば調べるほど沼にはまりそうなので、全体地図として一旦ここで締めます。気付きがあれば、追記します。