アルゴリズムの計算量の評価よく使われるO-記法関数の種類を示す。
これらの中でも特に重要なものには、個別の名称がついている(多項式時間など)。
以下、 nはアルゴリズムに入力されるデータのビット数を表す。
注意しなければならないのは、アルゴリズムに整数 N を入力するときである。N のビット数 n はおよそ log2 N なので、例えば「多項式時間」といったとき、これはN の多項式ではなく n の多項式を表す。
一般的ではないが、更に発散速度の速い関数も存在する（アッカーマン関数 A(m, n) など）。逆に更に発散速度の遅い関数として、逆関数である逆アッカーマン関数 α(n) などもあり、実際にあるアルゴリズムの計算量の見積りとして出現する。この関数は上界こそないものの、非常に発散速度が遅いために実用的には定数と見なされる (α(3) = 1, α(7) = 2, α(61) = 3, {\displaystyle \alpha (2^{2^{2^{65536}}}-3)=4}
, ...)。
, ...)。
0 件のコメント:
コメントを投稿