時間計算量
提供: cppreference.com
< cpp
アルゴリズムはどれも異なる計算量を持ちます。Nサイズの入力が与えられたとすると、それらは以下のように表現されます:
| 名前 | 早さ | 概要 | 数式 | 例 |
|---|---|---|---|---|
| 階乗時間※1(factorial time) | より遅い | Nの階乗に比例した時間を費やします(※2) | N! | 巡回セールスマン問題の総当たりによる解法 |
| 指数関数時間 | 遅い | 定数のN乗に比例した時間を費やします | KN | ルービックキューブの総当たりによる解法 |
| 多項式時間 | 早い | Nの定数乗に比例した時間を費します | NK | 比較ソート (バブル、挿入、選択ソート) |
| 線形対数時間※1(linearithmic time) | より早い | 多項式時間と線形時間の中間の時間を費やします | N * log(N) | 線形対数ソート※1 (クイックソート、ヒープソート、マージソート) |
| 線形時間 | さらに早い | Nに直接比例した時間を費やします | K * N | 配列走査 |
| 対数時間 | とても早い | Nの対数に比例した時間を費やします | K * log(N) | 2分探索 |
| 定数時間 | 最も早い | 入力がどんなに大きくても固定の時間を費やします | K | インデックスによる配列要素へのアクセス |
訳注：※1正確な数学用語求む ※2原文合ってますか？
[編集]計算量解析
異なる順序や集合の入力に対する操作は異なる計算量を持ちます。異なる時間計算量解析の手法は以下の通りです:
| 名前 | 概要 | 例 |
|---|---|---|
| 最善ケース | 可能な限り高速に処理されるケース | バブルソートの最善ケースの計算量はNです |
| 平均ケース | 起こりうる大多数の事例と同等の時間で処理されるケース | クイックソートの平均計算量はN * log(N)です |
| 最悪ケース | 可能な限り低速で処理されるケース | クイックソートの最悪ケースの計算量はN2です |
| 償却的な最悪ケース | 果てしなく大きな入力を受け取ったときの平均最悪ケース | vector::push_back()は償却的な最悪ケースの計算量はK(定数時間)です |
適切なアルゴリズムの選択は、どのようなケースとの遭遇をアプリケーションに期待しているかに依存します。たとえば、アプリケーションを悪意ある入力から守らなければならない場合、最悪ケースの計算量がN2の単純なクイックソート実装は避けられるでしょう。平均ケースの計算量が他のすべてのソートの中でもっとも早いものの一つであるにもかかわらずです。
