無限大における漸近挙動と計算量の見積り
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/03 02:49 UTC 版)
「ランダウの記号」の記事における「無限大における漸近挙動と計算量の見積り」の解説
O-記法はアルゴリズムの効率を解析するのに有用である。たとえば、あるサイズ n の問題(例えば処理すべきデータが n 個あるなど)を解くのに掛かる時間あるいは手順数が T(n) = 4n2 − 2n + 2 である場合を考える。 このとき、n を次第に大きくしていくと、 T(n) に対して n2 の項の影響が支配的になり、他の項はほとんど無視できるようになる（たとえば n = 500 としてみると、4n2 の項は 2n の項の実に1000倍であり、後者を無視しても式に与える影響は、計算量を考える上でほとんど無視できる）。 さらに、n3 や 2n といった他のオーダーの式と比較する分には係数も無関係になる（たとえば T(n) = 1,000,000n2 のように係数が大きい関数と、それより指数が1大きい U(n) = n3 を比較する。仮に n = 1,000,000 としてみると T(1,000,000) = 1,000,000×1,000,0002 = 1,000,0003 = U(1,000,000) だから、n > 1,000,000 の場合は常に U(n) > T(n) である。）。 こうして残る影響をすくい上げて、O-記法では T ( n ) ∈ O ( n 2 ) {\displaystyle T(n)\in O(n^{2})} と書いて、「n2 のオーダーである」と言い、これによってこのアルゴリズムの時間あるいは手順数T(n) の増加具合が n2 に支配されることを表現する。
※この「無限大における漸近挙動と計算量の見積り」の解説は、「ランダウの記号」の解説の一部です。
「無限大における漸近挙動と計算量の見積り」を含む「ランダウの記号」の記事については、「ランダウの記号」の概要を参照ください。
- 無限大における漸近挙動と計算量の見積りのページへのリンク
