=====時間計算量======

アルゴリズムはどれも異なる計算量を持ちます。Nサイズの入力が与えられたとすると、それらは以下のように表現されます:

^名前^早さ^概要^数式^例^
|階乗時間※1(factorial time)|より遅い|Nの階乗に比例した時間を費やします(※2)|  N!  |巡回セールスマン問題の総当たりによる解法|
|指数関数時間|遅い|定数のN乗に比例した時間を費やします|  K<sup>N</sup>  |ルービックキューブの総当たりによる解法|
|多項式時間|早い|Nの定数乗に比例した時間を費します|  N<sup>K</sup>  |比較ソート (バブル、挿入、選択ソート)|
|線形対数時間※1(linearithmic time)|より早い|多項式時間と線形時間の中間の時間を費やします|  N * log(N)  |線形対数ソート※1 (クイックソート、ヒープソート、マージソート)|
|線形時間|さらに早い|Nに直接比例した時間を費やします|  K * N  |配列走査|
|対数時間|とても早い|Nの対数に比例した時間を費やします|  K * log(N)  |2分探索|
|定数時間|最も早い|入力がどんなに大きくても固定の時間を費やします|  K  |インデックスによる配列要素へのアクセス|
訳注：※1正確な数学用語求む ※2原文合ってますか？

====計算量解析====

異なる順序や集合の入力に対する操作は異なる計算量を持ちます。異なる時間計算量解析の手法は以下の通りです:

^名前^概要^例^
|最善ケース|可能な限り高速に処理されるケース| バブルソートの最善ケースの計算量はNです|
|平均ケース|起こりうる大多数の事例と同等の時間で処理されるケース| クイックソートの平均計算量はN * log(N)です|
|最悪ケース|可能な限り低速で処理されるケース| クイックソートの最悪ケースの計算量はN<sup>2</sup>です|
|償却的な最悪ケース|果てしなく大きな入力を受け取ったときの平均最悪ケース| vector::push_back()は償却的な最悪ケースの計算量はK(定数時間)です|

適切なアルゴリズムの選択は、どのようなケースとの遭遇をアプリケーションに期待しているかに依存します。たとえば、アプリケーションを悪意ある入力から守らなければならない場合、最悪ケースの計算量がN<sup>2</sup>の単純なクイックソート実装は避けられるでしょう。平均ケースの計算量が他のすべてのソートの中でもっとも早いものの一つであるにもかかわらずです。