通信用語の基礎知識 IPv4
戻る
参加者募集中

オー記法

辞書:科学用語の基礎知識 算数・数学編 (NMATH)
読み:オーきほう
外語:O notation 英語
品詞:名詞

記事の有効期限について

この記事は更新履歴情報のない、旧形式項目です。久しく更新されておらず、古い記述を含む可能性があります。

更新すべき内容を見つけた場合は、ページ末の報告フォームよりお知らせください。また、現在当サイトは編集仲間を求めています

関数の増加的傾向を示す記法の一つ。小文字のoと区別するためにビッグオー(big-oh)記法と呼ぶことも多い。アルゴリズムの計算量の増加傾向を検討するのによく使われている。

たとえばf(n) = 2n4 + 50n2 + 200n + 3000 という関数がある場合、nが十分大きい場合は50n2、200n、3000といった数値は2n4の数値に比べて無視できるため、2n4の部分だけで関数の増加傾向が理解できるだろうと考える。

さらに2n4の2は定数倍項であるため、増加傾向の検討に必ずしも必要ない。そのため、通常はこの2も省略しn4だけで増加傾向を検討する。そのことを示すには、f(n) = O(n4)と書き、f(n)はn4のオーダーである、と表現する。

このような関数の省略を行なうことにより、数値の増加傾向の比較が簡単になるという利点がある。その代わり、実際の数値の正確さには欠けてしまう。

オー記法の定義は、関数f(n)、g(n)があり、f(n)≦cg(n)、n≧n0を満たすような定数cとn0が存在する時、f(n) = O[g(n)]。ただし、f(n) > 0、g(n) > 0。

計算量の増加傾向(下に行くほど増加傾向が高い)

  • c (cは定数, 以下同じ)
  • n
  • n log n
  • nc (c≧2)
  • cn
  • n!
関連する用語
計算量

コメントなどを投稿するフォームは、日本語対応時のみ表示されます


KisoDic通信用語の基礎知識検索システム WDIC Explorer Version 7.03 (16-May-2019)
Search System : Copyright © Mirai corporation
Dictionary : Copyright © WDIC Creators club