U「アルゴリズムって、プログラマーが知っていればいい話では？」と思っていました。でも診断士試験では「データをどう整理すると検索が速くなるか」という問いに答えられることが求められます。経営者がITベンダーと話すときに必要な共通言語として、アルゴリズムの基礎は知っておいて損はないと感じています。
この記事でわかること
- 主要なデータ構造（配列・スタック・キュー・連結リスト・木構造）の特徴
- ソートアルゴリズム（バブル・選択・挿入・クイック・マージ）の比較
- 探索アルゴリズム（線形探索・二分探索・ハッシュ）の違い
- 計算量（O記法）の読み方
- 流れ図（フローチャート）の記号と読み方
目次
データ構造——データの入れ物の形
| データ構造 | 特徴 | 主な用途 |
|---|---|---|
| 配列（Array） | 連続したメモリ領域。インデックスで直接アクセス可能（高速）。サイズ固定 | 成績リスト・座席番号管理 |
| スタック（Stack） | 後入れ先出し（LIFO：Last In First Out）。プッシュ（追加）とポップ（取出） | 「戻る」ボタンの履歴・関数呼び出しの管理 |
| キュー（Queue） | 先入れ先出し（FIFO：First In First Out）。エンキュー（追加）とデキュー（取出） | プリンターの印刷待ち・コールセンターの着信順 |
| 連結リスト | 各要素が次の要素へのポインタを持つ。挿入・削除が容易。ランダムアクセスは低速 | 動的なデータ管理 |
| 木（Tree）構造 | 階層的なデータ構造。二分探索木・ヒープ・B木など。探索・整列に効率的 | ファイルシステム・XMLのDOM・データベースのインデックス |
| ハッシュテーブル | キーをハッシュ関数で変換してデータを格納。平均O(1)で検索可能 | 辞書・連想配列・DBのインデックス |
スタックとキューの覚え方
スタック＝本の積み重ね：一番上に置いた本を一番最初に取る（LIFO）キュー＝レジの行列：先に並んだ人が先に会計できる（FIFO）
ソートアルゴリズム——データを並び替える方法
| アルゴリズム | 仕組み | 計算量（平均） | 特徴 |
|---|---|---|---|
| バブルソート | 隣接する要素を比較・交換を繰り返す | O(n²) | 実装が簡単。大規模データには不向き |
| 選択ソート | 未整列部分の最小値を選び先頭へ移動 | O(n²) | 交換回数が少ない。安定ではない |
| 挿入ソート | 要素を適切な位置に挿入していく | O(n²) | ほぼ整列済みのデータに強い。安定ソート |
| クイックソート | 基準値（ピボット）で分割・再帰的に整列 | O(n log n) | 実用的に最速クラス。最悪O(n²)になることも |
| マージソート | 分割→整列→統合の再帰的処理 | O(n log n) | 安定ソート。大規模データに向く。外部ソートに使われる |
| ヒープソート | ヒープ（優先度キュー）を使って整列 | O(n log n) | 最悪でもO(n log n)。追加メモリ不要 |
探索アルゴリズム——データを見つける方法
| アルゴリズム | 仕組み | 計算量 | 前提条件 |
|---|---|---|---|
| 線形探索（逐次探索） | 先頭から順に比較していく | O(n) | なし（整列不要） |
| 二分探索（バイナリサーチ） | 中央と比較し半分に絞り込む（再帰） | O(log n) | データが昇順または降順に整列済みであること |
| ハッシュ探索 | ハッシュ関数でキーから格納位置を計算 | O(1)（平均） | ハッシュテーブルの事前構築 |
計算量（O記法）の読み方
- O(1)：データ量に関わらず一定時間。最速（例：ハッシュ探索）
- O(log n)：対数。データが2倍になっても処理は1ステップ増えるだけ（例：二分探索）
- O(n)：データ数に比例。データが2倍→処理も2倍（例：線形探索）
- O(n log n)：効率的なソートはここが限界（例：クイックソート・マージソート）
- O(n²)：データが2倍→処理は4倍。大規模データには不向き（例：バブルソート）
流れ図（フローチャート）の記号
| 記号 | 図形 | 意味 |
|---|---|---|
| 端子 | 角丸長方形（楕円） | 開始・終了 |
| 処理 | 長方形 | 演算・代入などの処理 |
| 判断 | ひし形 | 条件分岐（Yes/No） |
| 入出力 | 平行四辺形 | データの入力・出力 |
| ループ端 | 六角形 | 繰り返し処理の開始・終了 |
| サブルーチン | 二重枠長方形 | 別に定義された処理の呼び出し |
Uのメモ
学習メモ
- スタック：LIFO（本の積み重ね）/ キュー：FIFO（レジの行列）
- 木構造：階層データ・DB索引 / ハッシュ：O(1)で検索
- ソート：バブル・選択・挿入=O(n²) / クイック・マージ・ヒープ=O(n log n)
- 探索：線形=O(n) / 二分=O(log n)（整列必要）/ ハッシュ=O(1)
- フローチャート：ひし形=判断（分岐）/ 長方形=処理 / 楕円=端子
