概要

情報技術の基礎として理解しておきたいアルゴリズムのうち、フローチャート、探索、整列、再帰、文字列処理を整理する。

アルゴリズムは、問題を解く手順を明確にしたものとなる。
アルゴリズムを理解するには、手順の意味だけでなく、データ数が増えたときの計算量や、処理の流れを正しく追えるかが重要になる。

この記事の構成

• フローチャート
  フローチャートを順にたどり、各処理の役割を整理。
• 探索アルゴリズム
  データ群から目的のデータを探すためのアルゴリズムで次の代表的なアルゴリズムがある。
• 整列アルゴリズム
  データを昇順または、降順にソートするためのアルゴリズムで次の代表的なアルゴリズムがある。
• 再帰アルゴリズム
  再帰アルゴリズム：その名の通り、 再帰（自分自身を呼出す）するアルゴリズム。
• 文字列処理のアルゴリズム
  文字列処理のアルゴリズム：文字列探索後に挿入、 削除、 置換、 連結等を行うアルゴリズム。

フローチャート

• フローチャート（流れ図）
  基本3構造と呼ばれる、順次、選択、繰返しを用いて、プログラムの処理の流れを図式化したもの。
  順次は、上から下へ順番に命令を実行する処理を指す。
  選択は、if文やswitch文等の分岐処理を指す。
  繰返しは、for文やwhile文等のループ処理を指す。
  

探索アルゴリズム

データ群から目的のデータを探すためのアルゴリズムで次の代表的なアルゴリズムがある。

※ \(n\) は、データの個数を表すものとする。
計算量については、
応用情報技術 - 情報理論 > 計算量 を参照。

• 線形探索
  先頭から順番に一つずつ評価して探索するアルゴリズム。

  計算量は、\(O\ (n)\) となる。

• 2分探索
  事前にデータを整列させた探索されるデータに対して中間データの比較を繰返して探索するアルゴリズム。

  計算量は、\(O\ (log\ n)\) となる。

• ハッシュ表探索
  ハッシュ関数を用いて探索するアルゴリズム。
  探索されるデータのハッシュテーブルに対して、探索するデータのハッシュ値でデータ（値）を逆引きし探索する。

  ハッシュ関数がキーを適切に分散させ、衝突が少ない場合の平均計算量は \(O\ (1)\) となる。
  ただし、多くのキーが同じ位置に衝突する場合は探索回数が増え、最悪計算量は \(O\ (n)\) となる。

• シノニム（synonym）
  ハッシュテーブルにおいて、異なるキーが同じハッシュ値になること。
  この状態を衝突という。

  ハッシュ表は、衝突が起こる前提で、次のチェイン法やオープンアドレス法などを用いてデータを区別。

• チェイン法（分離連鎖法）
  シノニム問題の解決法の一つ。

  ハッシュ値にシノニム（衝突）が発生した場合、個々のデータを連結リスト（互いに参照できる仕組みを持つ）で繋ぎ、衝突を解決する方法のこと。

• オープンアドレス法（ハッシュ法、閉番地法）
  シノニム問題の解決法の一つ。

  ハッシュ値にシノニム（衝突）が発生した場合、再ハッシュ（別バケットにデータを格納する）の繰返しにより、衝突を解決する方法のこと。

整列アルゴリズム

データを昇順または、降順にソートするためのアルゴリズムで次の代表的なアルゴリズムがある。

※ \(n\) は、データの個数を表すものとする。

• バブルソート
  隣合うデータを大小比較し、ソート順と逆ならば順番を入替えてソートするアルゴリズム。

  すべての隣合うデータに対して大小比較を繰返すため、平均・最悪計算量は \(O\ (n^2)\) となる。

• 挿入ソート
  整列済のデータに対して線形探索で挿入位置を決め、データを挿入してソートするアルゴリズム。

  挿入位置までの比較と要素の移動を繰り返すため、平均・最悪計算量は \(O\ (n^2)\) となる。
  ほぼ整列済みのデータに対しては高速に動作。

• 選択ソート
  未整列のデータ群からソート順に応じた最大値（最小値）を検索（特定）後、整列済データに分類し、ソートするアルゴリズム。

  最大値（最小値）の探索をデータ数分行うため、平均・最悪計算量は \(O\ (n^2)\) となる。

• クイックソート
  ピボット（基準値）を一つ決め、ピボットより小さい要素と大きい要素の部分列に分け、それぞれで同じ操作を繰り返すアルゴリズム。

  分割統治法を利用し、平均計算量は \(O\ (n\ log\ n)\) となる。
  ピボットの選び方とデータの並びによって分割が偏ると、最悪計算量は \(O\ (n^2)\) となる。

• シェルソート
  挿入ソートの改良版。
  一定間隔おきのデータを対象にした部分列をそれぞれ挿入ソートで整列させ、その間隔が1になるまで狭めてソートするアルゴリズム。

  計算量は間隔の選び方に依存するため、一律に \(O\ (n\ log\ n)\) とは言えない。

• ヒープソート
  選択ソートの改良版。
  未整列データでヒープを構成することによって、最大値（最小値）となる根を整列済データとし、未整列データがなくなるまで繰返しソートするアルゴリズム。

  計算量は、\(O\ (n\ log\ n)\) となる。

  ※ ヒープについては、応用情報技術 - データ構造 > ヒープ を参照。

• マージソート
  まず、未整列データを前後2つのグループに分け、この操作をデータ数が \(1\) になるまで再帰的に繰返す。
  次に、データ数が小さい方から順に前後2つのグループをソートしつつ併合（マージ）する操作を分割したグループ分、繰返してソートするアルゴリズム。

  クイックソートと同じ分割統治法を利用しており、計算量は、\(O\ (n\ log\ n)\) となる。
  ただし、マージに伴うメモリ消費が多い。

再帰アルゴリズム

• 再帰アルゴリズム
  その名の通り、再帰（自分自身を呼出す）するアルゴリズム。

  • 例：\(0\) を含む自然数 \(n\) に対して、\(n\) の階乗を返す関数 \(fact\ (n)\) を再帰的に定義。

  ※ Javaで書いた場合

  if (n == 0) {
      return 1;
  } else {
      return n * fact(n - 1);
  }
  

文字列処理のアルゴリズム

• 文字列処理のアルゴリズム
  文字列の探索、挿入、削除、置換、連結などを行うアルゴリズムの総称。
  ここでは、文字列探索のアルゴリズムについて、次の代表的な方法を扱う。

• 順次探索法
  探索対象の文字列の先頭から、探したいパターンを \(1\) 文字ずつ照合するアルゴリズム。

  • （＊1）探索
    探索対象の現在位置とパターンの先頭を合わせ、文字を順に照合する。

  • （＊2）照合判断
    

    • 照合一致の場合、探索対象とパターンの両方を次の文字へ進める。
      
    • 照合不一致の場合、パターンを先頭に戻し、探索開始位置を \(1\) 文字右へずらして照合し直す。

  探索対象の長さを \(n\)、パターンの長さを \(m\) とすると、最悪計算量は \(O\ (nm)\) となる。

• BM法（ボイヤームーア法）
  パターンの末尾から先頭へ向かって照合し、不一致時に不要な照合をスキップする文字列探索アルゴリズム。

  • （＊1）事前準備
    パターン内の文字位置を用いる不良文字規則と、一致済みの接尾部を用いる良い接尾辞規則のシフト表を準備する。

  • （＊2）探索
    探索対象とパターンの先頭位置を合わせ、パターンの末尾から左方向へ文字を照合する。

  • （＊3）照合判断
    

    • 照合一致の場合、パターンの一つ左の文字を続けて照合する。先頭まで一致すると検索成功となる。
      
    • 照合不一致の場合、事前に作成した表から求めた文字数だけパターンを右へずらし、照合し直す。

上記以外にも代表的なアルゴリズムとして、メモリ管理、データ圧縮、グラフ、近似/統計確率、図形描画、遺伝的なアルゴリズムなどがある。

まとめ

• 二分探索は整列済みデータを前提とし、ハッシュ表探索は平均的に高速だが衝突対策が必要になる。
• 再帰は問題を小さな同種の問題として解く表現で、無限に呼び出さないよう終了条件を明確にする。
• 文字列探索では、照合する方向や不一致時の移動方法によって処理効率が変わる。
• アルゴリズムはデータ数が増えたときの計算量の伸び方と、利用できる前提条件を合わせて比較。

参考文献

• 瀬戸 美月（\(2020\)）『徹底攻略 応用情報技術者教科書』株式会社インプレス
• Python公式ドキュメント - ソートのテクニック（日本語・整列処理の公式解説）
• NIST Dictionary of Algorithms and Data Structures - Binary search（英語・二分探索の公的用語定義）
• NIST Dictionary of Algorithms and Data Structures - Quicksort（英語・クイックソートの公的用語定義）
• NIST Dictionary of Algorithms and Data Structures - Boyer-Moore（英語・文字列探索の公的用語定義）