| cppreference.com -> 計算量 |
任意の与えられたアルゴリズムに対し、異なる速度の基準が存在する。 入力サイズを N とするとき、それらの尺度は次のように記述される:
| 名称 | 速度 | 解説 |
|---|---|---|
| 指数関数時間 | 遅い | 定数の N 乗 (K^N) に比例する時間を要する |
| 多項式時間 | 速い | N の定数乗に比例する時間を要する (N^K) |
| 線形時間 | さらに速い | N に比例する時間を要する (K * N) |
| 対数時間 | とても速い | N の対数に比例する時間を要する (log(N)) |
| 定数時間 | 最高速 | 入力サイズによらず、一定の時間を要する (K) |