ランダウの記号とは？わかりやすく解説

スターリングの公式はランダウの記号を用いて $\ln n!=n\ln n-n+O(\ln n)$

この記事には、過剰に詳細な記述が含まれているおそれがあります。
百科事典に相応しくない内容の増大は歓迎されません。内容の整理をノートで検討しています。（2016年1月）

関数 f(n) が他の関数の有限和で表せるとき(多項式であるとき)、その内最も発散速度の速い関数が f(n) のオーダーを決定づける。以下にその例を挙げる。

f(n)=9\log n+5(\log n)^{3}+3n^{2}+2n^{3}\in O(n^{3}).

例での場合、係数を無視してnに関する項を見ると、log n、(log n)³、n²、n³の4つが存在し、このうちn³が最も発散が速い。そのため、他のnに関する項に関わらず、オーダーはO(n³)とする。

特に、関数が n の多項式でおさえられるならば、n が無限大に発散するに従ってより低いオーダーの項まで無視できるようになる。

O(n^c) と O(cⁿ) は全く異なる。前者の定数 cがどれほど大きかろうと、後者の方がずっとずっと速く発散する。どのような定数 c に対しても n^cより速く発散する関数は超多項式 (superpolynomial) と呼ばれる。また、どのような定数 c に対しても cⁿ よりも遅く発散する関数は準指数関数 (subexponential) と呼ばれる。アルゴリズムの計算量が超多項式かつ準指数関数であることもあり得る。例えば、現在知られている内で最も早い因数分解のアルゴリズムもこれに含まれる。

O(log n) と O(log(n^c)) は全く等価である。なぜならば、log(n^c) = c log n より2つの指数関数は定数係数のみが異なり、これは big O-記法では無視されるからである。同様に異なる底を持つ対数関数も等価であるが、一方、異なる底を持つ指数関数は等価ではない。これはよくある勘違いである。例えば、2ⁿ と 3ⁿ は同じオーダーではない。

入力サイズの単位の変更は、アルゴリズムの計算量を変えるかもしれないしそうでないかもしれない。単位を変更するということは、関数に現れる全ての n にある定数を掛けることと同じである。例えば、アルゴリズムが n² のオーダーで動くとき、n を cn で置き換えれば計算量は c²n² となり、big O-記法では c² は無視されるので計算量は変化しない (c²n² ∈ O(n²))。しかし例えば 2ⁿ のオーダーで動くアルゴリズムでは、n を cn で置き換えると計算量は 2^cn = (2^c)ⁿ となる。これは 2ⁿ とは等しくない（もちろん、c = 1 の場合を除く）。

例

次の多項式関数を考える

{\begin{aligned}f(x)&=6x^{4}-2x^{3}+5,\\g(x)&=x^{4}.\end{aligned}}

このとき、f(x) のオーダーは O(g(x)) または O(x⁴) である。実際、オーダーの定義からこれはある定数 Cと x₀ が存在して、x₀ < x なる任意の x に対し |f(x)| ≤ C |g(x)| が成り立つことを意味するが、x > 1 において

{\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+2x^{3}+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&\leq 13x^{4}\\&\leq 13|x^{4}|\end{aligned}}

であるから、C = 13, x₀ = 1 とおけばよい。

リーマン予想が正しければ、x 以下の素数の個数 π(x) は次のように
$\pi (x)=\int _{2}^{x}{\frac {dt}{\log t}}+O({\sqrt {x}}\,\log x)$
と評価できる（素数定理も参照）。
バブルソートの時間的計算量を考えると、n 個の要素からなる列をソートするのに掛かる時間はO(n²) である。クイックソートを使えば、平均計算時間を O(n log n) に改善できる（但し最悪時にはO(n²)）。
n 次正方行列の固有値を求めるアルゴリズムは、少なくともその行列に含まれる n² 個の要素を読み取らなければならない。従って、固有値を求めるアルゴリズムの時間的計算量の下界は Ω(n²) である。

すなわち、一般的な行列に対してその固有値を計算するのに掛かる時間が n² のオーダーを下回るアルゴリズムは存在しない。

無限大における漸近挙動と計算量の見積り

O-記法はアルゴリズムの効率を解析するのに有用である。たとえば、あるサイズ n の問題(例えば処理すべきデータが n 個あるなど)を解くのに掛かる時間あるいは手順数が T(n) = 4n² − 2n + 2 である場合を考える。

このとき、n を次第に大きくしていくと、 T(n) に対して n² の項の影響が支配的になり、他の項はほとんど無視できるようになる（たとえば n = 500 としてみると、4n² の項は 2n の項の実に1000倍であり、後者を無視しても式に与える影響は、計算量を考える上でほとんど無視できる）。

さらに、n³ や 2ⁿ といった他のオーダーの式と比較する分には係数も無関係になる（たとえば T(n) = 1,000,000n² のように係数が大きい関数と、それより指数が1大きい U(n) = n³ を比較する。仮に n = 1,000,000 としてみると T(1,000,000) = 1,000,000×1,000,000² = 1,000,000³ = U(1,000,000) だから、n > 1,000,000 の場合は常に U(n) > T(n) である。）。

こうして残る影響をすくい上げて、O-記法では

T(n)\in O(n^{2})

と書いて、「n² のオーダーである」と言い、これによってこのアルゴリズムの時間あるいは手順数T(n) の増加具合が n² に支配されることを表現する。

参考文献

日本数学会編『岩波数学辞典』（第4版）岩波書店、2007年。 ISBN 978-4-00-080309-0。
de Bruijn, N. G. (1981). Asymptotic Methods in Analysis. Dover. ISBN 0-486-64221-6. Zbl 0556.41021
Graham, R. L.; Knuth, D. E.; Patashnik, O. (1994). Concrete Mathematics (Second ed.). Addison-Wesley. ISBN 0-201-55802-5
Marian Slodicka & Sandy Van Wontergem. Mathematical Analysis I. University of Ghent, 2004.
Donald Knuth (Apr.–June 1976). “Big Omicron and big Omega and big Theta”. ACM SIGACT News 8 (2): 18–24. doi:10.1145/1008328.1008329.
Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 1.2.11: Asymptotic Representations, pp.107–123.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 3.1: Asymptotic notation, pp.41–50.
Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X Pages 226–228 of section 7.1: Measuring complexity.
Jeremy Avigad, Kevin Donnelly. Formalizing O notation in Isabelle/HOL
Paul E. Black, "big-O notation", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 11 March 2005. Retrieved December 16, 2006.
Paul E. Black, "little-o notation", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Retrieved December 16, 2006.
Paul E. Black, "Ω", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Retrieved December 16, 2006.
Paul E. Black, "ω", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 29 November 2004. Retrieved December 16, 2006.
Paul E. Black, "Θ", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004. Retrieved December 16, 2006.

ランダウの記号とは？わかりやすく解説