概要

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

短い配列を使って探索・整列の途中状態を追い、候補を捨ててよい理由や再帰が終了する条件を確認する。手順とその手順が正しいための前提を組にして理解する。

この記事の構成

• フローチャート
  フローチャートを順にたどり、各処理の役割を整理。
• 探索アルゴリズム
  整列済み配列で候補を半分に絞り、二分探索に必要な前提を確認。
• 整列アルゴリズム
  データを昇順または降順にソートするためのアルゴリズムで次の代表的なアルゴリズムがある。
• 再帰アルゴリズム
  階乗の呼出しを展開し、終了条件へ近づく必要性を確認。
• 文字列処理のアルゴリズム
  文字列処理のアルゴリズム：文字列探索後に挿入、 削除、 置換、 連結等を行うアルゴリズム。

フローチャート

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

探索アルゴリズム

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 二分探索で半分を捨ててよい理由
  昇順の [2, 5, 8, 12, 16, 23, 38] から23を探す。中央の12より23が大きいので、12以下の左側を候補から除ける。残る [16, 23, 38] の中央は23となり、2回の比較で見つかる。

  この推論は中央より左の値がすべて中央以下であることを使っている。未整列の [12, 2, 23, 5, 16, 8, 38] に同じ処理をすると、中央の5を見て左側を捨てた時点で23を失う。二分探索の高速さは整列という前提と引き換えに得られる。

整列アルゴリズム

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

※ \(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)\) となる。
  ただし、マージに伴うメモリ消費が多い。

• 挿入ソートを一段ずつ追う
  [5, 2, 4] を昇順に並べる。先頭の5を整列済みと考え、2を挿入するときは5を右へずらして [2, 5, 4] にする。次に4を入れるときは5だけをずらし、2の後ろへ置いて [2, 4, 5] にする。

  すでに昇順なら各要素の挿入位置をすぐ確かめられる。一方、逆順では右へずらす数が1個、2個、…と増え、合計は \(n(n-1)/2\) 個になる。この違いから同じ挿入ソートでも入力の並びによって処理量が大きく変わることが分かる。

  同じキーを持つ要素の順序を保ちたい場合は、挿入対象より 大きい 要素だけをずらす。等しい要素まで追い越して挿入すると、安定性を失う場合がある。

再帰アルゴリズム

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

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

  ※ Javaで書いた場合

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

• 呼出しを展開すると終了条件の役割が見える
  階乗の例で fact(3) を呼ぶと、 3 * fact(2) → 3 * 2 * fact(1) → 3 * 2 * 1 * fact(0) と展開される。 fact(0) が1を返すので、戻りながら計算すると6になる。

  この関数の前提は引数が0以上の整数であること。−1から1ずつ減らしても0には到達せず、終了条件を満たさない。また、正しい終了条件があっても非常に大きい引数では呼出しの深さや整数型の範囲が制約になる。「結果を小さい問題で表せること」と「実際に終了条件へ近づくこと」を両方確認する必要がある。

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

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

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

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

  • （＊2）照合判断
    

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

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

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

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

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

  • （＊3）照合判断
    

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

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

• 一致しない文字から調べなくてよい位置を判断する
  文字列 ABXCAT からパターン CAT を探す。先頭の ABX に合わせ、パターン末尾のTと本文のXを比較すると不一致になる。Xはパターン内に一度も現れないため、このXを含む位置合わせは一致しないと分かる。

  そこでパターンを3文字分進め、次の CAT と比較できる。これはBM法の不一致文字に基づく移動の考え方である。常に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（英語・文字列探索の公的用語定義）