時間計算量

アルゴリズムの実行に必要な計算ステップ数を入力サイズの関数として表したもの。オーダー記法O(n)で表現され、O(1)、O(log n)、O(n)、O(n log n)、O(n²)などがある。アルゴリズムの効率を評価する基本指標。

アルゴリズムの実行に必要な手間を、入力データの大きさnに対する増え方で表したもの。処理時間を表す時間計算量と、必要な記憶領域を表す領域計算量があり、O(n)、O(n log n)、O(n²)のように最も影響の大きい項だけを残したオーダ記法で表す。

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

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

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

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

データの列を先頭から順に1つずつ調べて、目的のデータを探す方法。データが整列されていなくても使えるが、比較の回数は平均でn/2回、計算量はO(n)で、データが多いと時間がかかる。