計算量

アルゴリズムの実行に必要な時間や空間の量をオーダー記号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)、O(n log n)、O(n²)のように最も影響の大きい項だけを残したオーダ記法で表す。

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

最適化問題を部分問題に分割し、各部分問題の解を記憶しながら全体の最適解を求めるアルゴリズム設計手法。重複する部分問題を再計算せずに済むため効率的。ナップサック問題や最短経路問題に応用される。

直前の2項を足した値が次の項になる数列。1,1,2,3,5,8,13…と続く。再帰処理の例題として頻出で、素直に再帰で書くと同じ計算を何度も繰り返すため、途中結果を保存する動的計画法で高速化できる。

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

隣接する要素を比較して交換を繰り返すことでデータを整列するアルゴリズム。平均・最悪計算量ともにO(n²)で効率は良くないが、アルゴリズムが単純で理解しやすい。安定ソート。

未整列部分から最小値（または最大値）を見つけて先頭に移動する操作を繰り返す整列アルゴリズム。計算量はO(n²)で、交換回数が少ないがデータ比較は多い。不安定ソート。