計算量

• 時間計算量(Time complexity)
• 空間計算量(Space complexity)

アルゴリズムイントロダクションより引用

記法

$O$-notation

• 関数の漸近的振る舞いの上界(Upper-bound)を特徴づける。上から抑える。
  • 関数が最高次の項から決まる増加率を超える速度では増加しないことを表す
  • 例: $7n^2+4n+3$: $n^2$を超える速度では増加することがない
    • 同様に$n^3$も超えることがないので、$O(n^2),O(n^3),O(n^4)...$はすべて正しい
• 定義
  • 与えられた関数$g(n)$に対して、表記$O(g(n))$は関数の集合$O(g(n))=\{f(n)|\exists c,n_o,\forall n>n_0,cg(n)\ge f(n)\ge 0\}$
    • (ある正の定数$c,n_0$が存在して、全ての$n\ge n_0$に対して$cg(n)\ge f(n)\ge 0$を満たす)

$\Omega$-notation

• 下界(Lower-bound)を特徴づける。下から抑える。
• 関数が、最高次の項から決まる増加率と少なくとも同じ速度で増加することを示す
• 定義
  • 与えられた関数$g(n)$に対して、表記$\Omega (g(n))$は関数の集合$\Omega (g(n))=\{f(n)|\exists c,n_0,\forall n\ge n_0,f(n)\ge cg(n)\ge 0\}$

$\Theta$-notation

• 関数の漸近的振る舞いのタイトな限界(Tight-bound)を特徴づける。上下から抑える。
  • 関数が、高次の項から決まる増加率と正確に同じ速度で増加することを示す。
  • 関数の増加率が上からある定数倍の範囲内に入り、下からもある定数倍の範囲内にはいっていることを示す(2つの定数は異なっていてよい)
  • $O(f(n))$かつ$\Omega (f(n))$であれば、$\Theta (f(n))$
• 定義
  • 与えられた関数$g(n)$に対して、表記$\Omega (g(n))$は関数の集合$\Omega (g(n))=\{f(n)|\exists c_1,c_2,n_0,\forall n\ge n_0,c_{2}g(n)\ge f(n)\ge c_{1}g(n)\ge 0\}$