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

オーダー量

提供: kimoto's wiki

2013年7月24日 (水) 05:44時点におけるKimoto (トーク | 投稿記録)による版
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)

簡単にまとめると

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

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