一般的なオーダー
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/03 02:49 UTC 版)
計算機科学、特に計算量理論、アルゴリズム論、暗号理論では、アルゴリズムの計算時間を評価するのに O-記法を頻繁に用いる。 アルゴリズムの計算量の評価よく使われるO-記法関数の種類を示す。 これらの中でも特に重要なものには、個別の名称がついている(多項式時間など)。 以下、 nはアルゴリズムに入力されるデータのビット数を表す。 注意しなければならないのは、アルゴリズムに整数 N を入力するときである。N のビット数 n はおよそ log2 N なので、例えば「多項式時間」といったとき、これはN の多項式ではなく n の多項式を表す。 記法名称アルゴリズムの例 O ( 1 ) {\displaystyle O\left(1\right)} 定数時間 (Constant time) （整数の）偶奇判別 O ( log ∗ n ) {\displaystyle O\left(\log ^{*}n\right)} 反復対数（英語版） (iterated logarithmic) Hopcroft, Ullmanによる素集合データ構造における探索アルゴリズム O ( log n ) {\displaystyle O\left(\log n\right)} 対数 (logarithmic) ソート済み配列における二分探索 O ( n c ) , 0 < ∃ c < 1 {\displaystyle O\left({n^{c}}\right),0<\exists c<1} 分数指数関数 (fractional power) kd木上の探索 O ( n ) {\displaystyle O\left(n\right)} 線形関数 (linear) 非ソート配列上の探索、離散ウェーブレット変換 O ( n log n ) {\displaystyle O\left(n\log n\right)} 準線形、線形対数 (linearithmic, loglinear, or quasilinear) ヒープソート、高速フーリエ変換 O ( n 2 ) {\displaystyle O\left({n^{2}}\right)} 二乗時間 (quadratic) 挿入ソート、離散フーリエ変換 O ( n c ) , ∃ c ≥ 1 {\displaystyle O\left({n^{c}}\right),\exists c\geq 1} 多項式時間 (polynomial) ワーシャル-フロイド法 O ( 2 n ) {\displaystyle O{(2^{n})}} 指数時間 (exponential, geometricとも) （現在最も速い）巡回セールスマン問題の（厳密解の）解法 O ( n ! ) {\displaystyle O\left(n!\right)} 階乗関数 (factorial, combinatorialとも) 2つの論理式の同型判定、巡回セールスマン問題の（可能）解の枚挙 O ( 2 c n ) ∃ c > 0 {\displaystyle O\left(2^{c^{n}}\right)\exists c>0} 二重指数時間 AC単一化子の完備集合の探索 一般的ではないが、更に発散速度の速い関数も存在する（アッカーマン関数 A(m, n) など）。逆に更に発散速度の遅い関数として、逆関数である逆アッカーマン関数 α(n) などもあり、実際にあるアルゴリズムの計算量の見積りとして出現する。この関数は上界こそないものの、非常に発散速度が遅いために実用的には定数と見なされる (α(3) = 1, α(7) = 2, α(61) = 3, α ( 2 2 2 65536 − 3 ) = 4 {\displaystyle \alpha (2^{2^{2^{65536}}}-3)=4} , ...)。
※この「一般的なオーダー」の解説は、「ランダウの記号」の解説の一部です。
「一般的なオーダー」を含む「ランダウの記号」の記事については、「ランダウの記号」の概要を参照ください。
- 一般的なオーダーのページへのリンク
