計算量（オーダ記法）

アルゴリズムが処理に要する時間や記憶領域が、入力データの量nに応じてどう増えるかを表す尺度。定数倍などを無視した増え方をO(n)やO(n log n)のようなオーダ記法で示す。処理時間を表す時間計算量と、必要な記憶量を表す領域計算量がある。

アルゴリズムの実行に必要な時間や空間の量をオーダー記号O(n)で表現したもの。時間計算量と領域計算量があり、入力サイズnに対する増加傾向でアルゴリズムの効率を評価する。O(1)<O(log n)<O(n)<O(n log n)<O(n^2)<O(2^n)の順に計算量が大きい。

アルゴリズムが処理に要する時間（時間計算量）や記憶領域（領域計算量）が、入力の大きさnに対してどう増えるかを表したもの。定数倍や低い次数の項を省いて増え方だけを示すオーダ記法（O記法）で表し、O(1)＜O(log n)＜O(n)＜O(n log n)＜O(n²)＜O(2ⁿ)の順に増え方が大きい。データ量が増えたときの処理時間の見積もりや、アルゴリズムの選択に使う。

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

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