計算量

時間計算量（time complexity）、領域計算量（space complexity）を久しぶりに扱ったのでラウダウの記号（Landau notations）について復習した．

Wikipediaを見るといいが、一応メモってみた．

• f(n)=O(g(n))
  • 上限を表す
  • ∃(k>0),n_0: ∀(n>n_0)|f(n)|≦|g(n)k|
• f(n)=Ω(g(n))
  • 下限を表す
  • ∃(k>0),n_0: ∀(n>n_0)|g(n)k|≦|f(n)|
• f(n)=Θ(g(n))
  • イコールを許さない上限かつ下限を表す
  • ∃(k_1,k_2>0),n_0: ∀(n>n_0)|g(n)k_1|<|f(n)|<|g(n)k_2|
• f(n)=o(g(n))
  • イコールを許さない上限を表す（任意のkもポイント）
  • ∀(k>0),∃n_0: ∀(n>n_0)|f(n)|<|g(n)k|
• f(n)=ω(g(n))
  • イコールを許さない下限を表す（任意のkもポイント）
  • ∀(k>0),∃n_0: ∀(n>n_0)|g(n)k|<|f(n)|
• f(n)〜g(n)
  • lim_{n->∞}{f(n)/g(n)}=k,0