注意: このページは最後に更新されてから 1445 日が経過している記事です。 文章が腐敗している可能性があります。その点を考慮した上で確認ください。

オーダー量

提供: kimoto's wiki

簡単にまとめると

  • Θ(n)はnが増加していった時に特定の範囲内(上界と下界)に収まる性質があるということ
  • O(n)はnが増加していった時に上界のみについて関心がある時に使う
  • o(n)はO(n)と違い、上界自体を含まない。(<= ではなく < であるということ)
  • Ω(n)は下界のみに関心がある時に使う
  • ω(n)は下階のみに関心があり、下界自体を含まないときに使う (<= ではなく < であるということ)

つまり、Θ(n) というのは O(n) でもあり ω(n) でもある。