線形探索法

データの先頭から順に1つずつ目的の値と比較して探索するアルゴリズム。実装が簡単だが、データ量に比例して探索時間が増加するため、大量のデータには不向きである。

データを先頭から順に目的の値と比較していく探索アルゴリズム。計算量はO(n)。データが整列されていなくても使用できるが、データ数が多い場合は非効率。逐次探索とも呼ばれる。

データの先頭から順に1つずつ目的の値と比較していく探索の方法で、逐次探索ともいう。データが整列していなくても使え、データ数nに対して平均の比較回数はn/2、計算量はO(n)である。末尾に探す値を置いて終了判定を省く番兵法で処理を速くできる。

アルゴリズムの実行に必要な処理の手間（基本操作の回数）を、入力データの大きさnの関数として表したもの。オーダ記法で表し、例えば線形探索はO(n)、2分探索はO(log n)になる。

アルゴリズムの実行に必要な記憶領域（メモリ）の大きさを、入力データの大きさnの関数として表したもの。オーダ記法で表し、作業用の配列を必要とするマージソートはO(n)になる。時間計算量と引換えになることが多い。

隣り合う要素を比較し、順序が逆なら交換する操作を、列の端から端まで繰り返して整列するアルゴリズム。仕組みは単純だが、計算量はO(n²)で、大量のデータには向かない。

未整列の部分から最小（または最大）の要素を選び、未整列部分の先頭と交換する操作を繰り返して整列するアルゴリズム。交換の回数は少ないが、比較の回数が多く、計算量はO(n²)である。

整列済みの部分に、未整列部分の先頭の要素を適切な位置に挿入する操作を繰り返して整列するアルゴリズム。計算量はO(n²)だが、ほぼ整列済みのデータに対しては高速に動作する。

整列済みのデータの列の中央の値と目的の値を比べ、探す範囲を半分ずつに絞り込んでいく探索方法。比較の回数は最大でもおよそlog₂n回、計算量はO(log n)と高速だが、データがあらかじめ整列されている必要がある。