アルゴリズム

■ 線形探索法。Linear Search。

  あるデータ配列から特定の要素を検索する場合、
  データの先頭から順番に1つずつ要素を比較していく方法
  (書類の山から目的のものを探すとき、一番上から順に見ていくのと同じ)。

  線形探索を用いた場合の平均的な比較回数は、
  データ総数がn個とすると、1/2×n回である。
  すなわち、線形検索の処理時間はnに比例する。

  線形探索は、データが使用頻度順に格納されている場合に特に適している。
  この場合、平均比較回数は1/2×n回より少なくなる。

■ 2分探索法。Binary Search。

  あるデータ配列から特定の要素を検索する場合、
  探索範囲を半分づつ狭めて行う探索。

  2分探索法では、
  レコードをあらかじめキーの値に関して昇順(または降順)に並べておく。
  そして検索を行う際には、
  まず探索範囲の中間に位置するレコードのキーと探索対象レコードのキーとを比較し、
  探索するキーの方が小さい場合は次の探索範囲をデータ配列の前半部とし、
  大きい場合は後半部とする。

  2分探索法を用いた場合の平均探索回数は、
  データ総数がn個の場合、log2n(小数点以下切捨て)である。
  また、最大比較回数は平均比較回数+1となる。

■ ハッシュ法。Hash Method。

  あるデータ配列から特定の要素を検索する場合、
  各レコードのキーの値にハッシュ関数(modなど)を掛けて格納先のアドレスを算出し、
  直接に探索する方法。

  ハッシュ法を用いる場合には、データを格納する際に、
  探索時に使用するのと同じハッシュ関数で格納先のアドレスを算出し、
  そのアドレス位置にデータを格納しておく必要がある。

  ハッシュ法は、
  文字列などのようにデータひとつあたりが比較的長い場合に特に有効である。
  ただしハッシュ法では、異なったキーから同一アドレスが算出される
  「シノニム」が発生する場合がある。

■ 逆ポーランド表記法。Reverse Polish Notation 

  加減乗除などの演算子を、対象となる変数(オペランド)の後ろに置く、算術式の表記法。
  括弧()なしで数式を表現できる点が最大の特徴になっている。
  Ex) (A+B)×(C+D)/(A-D)= AB+CD+×AD-÷

  この表記法は，ポーランドの論理学者J.Lukasiewiczが使用したもので、
  後置表記法とも呼ばれる。主にコンピュータ内部で使われる。
  ()がないため、コンパイラ等で演算処理する場合に、スタックを使って簡単に計算できる。

以上。

2004/03/10 pm