アルゴリズム
アルゴリズムとは簡単にいうと、何かを作成する際の手順のことを言う。
線形探索法
線形探索法はあるものを探すときに、初めから直線的に探すという方法である。
この方法のメリットとしては、探したいものの規模が小さい、もしくは初めのにあるとわかっている場合には速く見つけることができる。
二分探索法
二分探索法は、探す対象が含まれているデータを何度も二等分して、徐々に絞っていき探していくという方法である。
この方法のメリットとしては、探したいものの規模が大きい、もしくはどの辺りにあるのかの検討がついていないときに有効である。
アルゴリズムの三大処理
アルゴリズムには基本的に三つの処理がある。
順次処理
処理を記述した順番に実行する
分岐処理
条件により処理の流れを変える。
繰り返し処理
条件が成立する間処理を繰り返す。
正当性と停止性
-
アルゴリズムは、与えられた課題に対して正しい結果をもたらさなければなりません。これを、アルゴリズムの正当性と言います。アルゴリズムにおいてその時点において、満たさなければならない条件が成立しているかどうかを判定し、正当性があることを保障しなければならないのです。
-
アルゴリズムの停止性とは、いかなる条件の入力値が与えられても、有限時間内に必ず正しく停止することを保証することで示されます。アルゴリズムの停止性の証明には、反復処理の終了条件の判定に使用される変数などを見て、必ず有限回数の繰り返しで終了条件が成立するいことを証明する方法があります。