ランダウの記号

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ランダウの漸近記法（ぜんきんきほう、asymptotic notation）は、関数極限における漸近挙動、すなわち値の変動のおおよその評価を与えるための記法である。ポール・バッハマンによって発明され、エドムント・ランダウが広めた。ランダウ記号 (Landau symbol)、ランダウ記法 (Landau notation) あるいは主要な記号として O を用いることから（ランダウの）O-記法などともいう。

[編集] 概要

変数の無限大あるいは無限小の変動に対する関数の挙動を、ある程度わかりやすい別の関数を目安にして記述する目的で用いられる。解析学では誤差項を記述するためによく使われる。また、離散的な値をとる変数を持つ関数（数列とみなして差し支えない）を考えることで数列の離散的な挙動も記述できる。特に計算理論では計算量を評価するために一般的に用いられる。

記号 O は通常、関数の大きさを上からの漸近的な上界を別のわかりやすい関数によって記述するために用いられる。同様に上界や下界あるいはその両側からの評価を様々に与えることで、o, Ω, ω, Θ といった類似記法が定義される。O-記法を簡略的に流用して漸近的 tight bound（比が有限かつ有界、この場合下限が0であることも発散に含む）を記述することも一般に行われるが、もっと正確に漸近的に漸近的 tight bound であることを明示するならば Θ-記法を用いる。

O-記法は大きく二つの分野で用いられる。数学では、無限級数（とくに漸近級数）を打ち切ったときの剰余項の特徴づけなどに使われる。また計算機科学ではアルゴリズムの計算量の解析に用いられる。

この記法はドイツの数論家であるポール・バッハマンによって1894年に彼の著書『解析数論』(Analytische Zahlentheorie) の第二巻で初めて導入された（1892年に著された第一巻では用いられていない）。この記法が一般に広まるのは、別のドイツ人数論家であるエドムント・ランダウの仕事によるもので、ランダウの記号と呼ばれる所以である。「程度」（オーダー）を意味するこの O はもとは大文字のオミクロンであったが、今日では形の似たラテンアルファベットの大文字オーと同一視され、オーも用いられる。しかし、数字の 0 では決してない。

この記法には二つ、形式的には近いが確かに異なる用法がある。無限大に関する漸近挙動と無限小に関する漸近挙動である。この差異は原理的なものではなくあくまで応用上のもので、「O-記法」の定義は、関数に対して引数の極限をとる際の行き先の違いを除いて、どちらの場合も同じものである。

[編集] 無限大における漸近挙動

O-記法はアルゴリズムの効率を解析するのに有用である。たとえば、あるサイズ n の問題を解くのに掛かる時間あるいは手順数が T(n) = 4n² - 2n + 2 と求まったとき、n を次第に大きくしていくと n² の項ばかり効いてくるようになり他の項はほとんど無視できるようになる（n = 500 としてみると、4n² の項は 2n の項の実に1000倍であり、後者を無視しても式に与える影響は計算量を考える上でほとんど無視できる程度である）。さらに、n³ や 2ⁿ といった他のオーダーの式と比較する分には係数も無関係になる。たとえ T(n) = 1,000,000n² だったとしても、U(n) = n³ であれば、T(1,000,000) = 1,000,000³ = U(1,000,000) だから、n が 1,000,000 を超えて大きくなれば常に後者のほうが大きいことになる。

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

$T(n)\in O(n^2)$

と表して、このアルゴリズムの計算量は「n² のオーダーである」と言い表す。

[編集] 無限小に対する漸近挙動

O-記法は数学的な関数の近似における誤差項の記述にも使われる。例えば

$e^x=1+x+\frac{x^2}{2}+O(x^3)\qquad\hbox{as}\ x\to 0$

なる式は、e^x − (1 + x + x²/2) という差（誤差）の絶対値が 0 の近くの x については |x|³ の適当な定数倍よりも小さいということを意味する。

[編集] 厳密な定義

f(x) と g(x) は実数からなるある集合上で定義されているとするとき、「f(x) が x → ∞ のとき O(g(x)) 程度である」ということを

∃x₀, ∃M > 0 such that |f(x)| ≤ M|g(x)| for any x > x₀

となることとして定める。また、ある実数 a の付近での挙動を記述するならば「f(x) が x → a のとき O(g(x) のオーダーである」というのを

∃δ > 0, ∃M > 0 such that |f(x)| ≤ M|g(x)| for any x where |x − a| < δ

であることと定める。g(x) が a の十分近くで 0 にならないならこれらの定義を上極限を使って統一的に記述できる。つまり「f(x) が x → a のとき O(g(x) の程度である」とは

$\limsup_{x\to a} \left|\frac{f(x)}{g(x)}\right| < \infty.$

が満たされることである。

数学では、無限大の近くや a の近くという二種類の漸近挙動を両方考えるが、計算量理論では無限大での漸近挙動がもっぱら扱われる。もっといえば、正値関数のみを扱うことも多く、その場合絶対値記号すら忘れてよい。

[編集] 記法の問題

上で定義された「f(x) が O(g(x)) の程度である」という言及はしばしば "f(x) = O(g(x))" と記される。これは少し紛らわしい記法の濫用で、二つの関数が等しいという意味ではないし、O(g(x)) があるせいで対称性も持たない。

$O(x) = O(x^2)\mbox{ but }O(x^2)\ne O(x)$ .

こういった理由から、集合の記法を用いて f ∈ O(g) と書くものもある。この場合、O(g) は g によって支配される関数全体の集合と考えていることになる。

もっとややこしい使い方としては、O( ) が等式の異なる場所に複数、もちろん両辺にわたって複数回現れるなどというものもある。例えば、以下は n → ∞ で正しい内容を記述している。

(n + 1) 2 = n 2 + O (n)

$(n+O(n^{1/2}))(n + O(\log\,n))^2 = n^3 + O(n^{5/2})$

n O (1) = O (e n)

ここでの式の意味は、次のように解釈する。左辺の O() を満足する「どんな」関数に対しても、右辺の O() を満足する「ある」関数をとって、それらの関数を代入した等式の両辺が等しいようにできる。例えば三つの目の式ならば、「どんな関数 f(n) = O(1) に対しても、g(n) = O(eⁿ) なるもののうちに、n^f(n) = g(n) を満たすものを選びうる」となる。上記の集合記法ならば、「左辺で表される関数のクラスは右辺で表される関数のクラスの部分集合になる」という意味に取れる。

[編集] 一般的なオーダー

Here is a list of classes of functions that are commonly encountered when analyzing algorithms. All of these are as n increases to infinity. The slower-growing functions are listed first. c is an arbitrary constant.

記法	名称	例
$\mathcal{O}\left(1\right)$	constant	Determining if a number is even or odd
$\mathcal{O}\left(\log^* n\right)$	iterated logarithmic	The `find` algorithm of Hopcroft and Ullman on a disjoint set
$\mathcal{O}\left(\log n\right)$	logarithmic	Finding an item in a sorted list with the binary search algorithm
$\mathcal{O}\left(\left(\log n\right)^c\right)$	polylogarithmic	Deciding if n is prime with the AKS primality test
$\mathcal{O}\left({n^c}\right), 0<c<1$	fractional power	searching in a kd-tree
$\mathcal{O}\left(n\right)$	linear	Finding an item in an unsorted list
$\mathcal{O}\left(n\log n\right)$	linearithmic, loglinear, or quasilinear	Sorting a list with heapsort, computing a FFT
$\mathcal{O}\left({n^2}\right)$	quadratic	Sorting a list with insertion sort, computing a DFT
$\mathcal{O}\left({n^c}\right), c>1$	polynomial, sometimes called algebraic	Finding the shortest path on a weighted digraph with the Floyd-Warshall algorithm
$\mathcal{O}\left({c^n}\right)=2^{O(n)}$	exponential, sometimes called geometric	Finding the (exact) solution to the traveling salesman problem
$\mathcal{O}\left(n!\right)$	factorial, sometimes called combinatorial	Determining if two logical statements are equivalent [1], traveling salesman problem, or any other NP Complete problem via brute-force search
$\mathcal{O}\left(2^{c^n}\right)$	double exponential	Finding a complete set of associative-commutative unifiers [2]

Not as common, but even larger growth is possible, such as the single-valued version of the Ackermann function, A(n,n). Conversely, extremely slowly-growing functions such as the inverse of this function, often denoted α(n), are possible. Although unbounded, these functions are often regarded as being constant factors for all practical purposes.

[編集] 例

Take the polynomials:

f (x) = 6 x 4 - 2 x 3 + 5,

g (x) = x 4 .

We say f(x) has order O(g(x)) or O(x⁴). From the definition of order, |f(x)| ≤ C |g(x)| for all x>1, where C is a constant.

Proof:

$|6x^4 - 2x^3 + 5| \le 6x^4 + 2x^3 + 5 \,$ where x > 1

$|6x^4 - 2x^3 + 5| \le 6x^4 + 2x^4 + 5x^4 \,$ because x³ < x⁴, and so on.

$|6x^4 - 2x^3 + 5| \le 13x^4 \,$

$|6x^4 - 2x^3 + 5| \le 13 \,|x^4 |. \,$ where C = 13 in this example

リーマン予想が正しければ、x以下の素数の個数π(x)は次のように評価できる（素数定理も参照）。

$\pi(x) = \int_2^x\frac{dt}{\log t} + O(\sqrt{x}\log x)$

バブルソートの時間的計算量を考えると、n個の要素からなる列をソートするのに掛かる時間はO(n²)である。クイックソートを使えば、平均計算時間をO(n log n)に改善できる。

$n$ 次正方行列の固有値を求めるアルゴリズムは、少なくともその行列に含まれる $n 2$ 個の要素を読み取らなければならない。従って、固有値を求めるアルゴリズムの時間的計算量の下界は $Ω(n 2)$ である。すなわち、どんなに良いアルゴリズムであったとしても、一般に固有値を計算するのに掛かる時間が $n 2$ のオーダーを下回ることはない。

[編集] 性質

If a function f(n) can be written as a finite sum of other functions, then the fastest growing one determines the order of f(n). For example

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

In particular, if a function may be bounded by a polynomial in n, then as n tends to infinity, one may disregard lower-order terms of the polynomial.

$O (n c)$ and $O (c n)$ are very different. The latter grows much, much faster, no matter how big the constant c is (as long as it is greater than one). A function that grows faster than any power of n is called superpolynomial. One that grows slower than any exponential function of the form $c n$ is called subexponential. An algorithm can require time that is both superpolynomial and subexponential; examples of this include the fastest known algorithms for integer factorization.

$O (log n)$ is exactly the same as $O (log(n c))$ . The logarithms differ only by a constant factor, (since $log(n c) = c log n)$ and thus the big O notation ignores that. Similarly, logs with different constant bases are equivalent. Exponentials with different bases, on the other hand, are not of the same order; assuming that they are is a common mistake. For example, $2 n$ and $3 n$ are not of the same order.

Changing units may or may not affect the order of the resulting algorithm. Changing units is equivalent to multiplying the appropriate variable by a constant wherever it appears. For example, if an algorithm runs in the order of n², replacing n by cn means the algorithm runs in the order of $c 2 n 2$ , and the big O notation ignores the constant $c 2$ . This can be written as $c^2n^2 \in \mathcal{O}(n^2)$ . If, however, an algorithm runs in the order of $2 n$ , replacing n with cn gives $2 c n = (2 c) n$ . This is not equivalent to $2 n$ (unless, of course, c=1).

積

f 1 (n) f 2 (n) = O (g 1 (n) g 2 (n))

和

O (f (n)) + O (g (n)) = O (max{ | f (n) | , | g (n) | })

定数倍

$O(k g(n)) = O(g(n)),\quad k \ne 0$

Other useful relations are given in section Big O and little o below.

[編集] その他の漸近記法

O-記法は関数比較のための漸近記法として最も一般に用いられるものであるが、多くの場合に漸近的な両側有界性を表すために Θ に置き換えられる。ここではランダウの記号として知られるいくつかの異なる記法を記す。

記法	意味	定義	ε-δ
$f(n) \in O(g(n))$	漸近的に上に有界	$\limsup_{n \to \infty} \left\|\frac{f(n)}{g(n)}\right\| < \infty$	∃M > 0, ∃x₀ such that \|f(x)\| ≤ M\|g(x)\| for all x > x₀.
$f(n) \in \Omega(g(n))$	漸近的に下に有界	$\liminf_{n \to \infty} \left\|\frac{f(n)}{g(n)}\right\| > 0$	∃M > 0, ∃x₀ such that \|f(x)\| ≥ M\|g(x)\| for all x > x₀.
$f(n) \in \Theta(g(n))$	漸近的に両側に有界	$\begin{align} 0 &< \liminf_{n \to \infty} \left\|\frac{f(n)}{g(n)}\right\| \\ &\quad \leq \limsup_{n \to \infty} \left\|\frac{f(n)}{g(n)}\right\|< \infty \end{align}$	f(n) ∈ O(g(n)) かつ f(n) ∈ Ω(g(n))
$f(n) \in o(g(n))$	漸近的に消える	$\lim_{n \to \infty} \left\|\frac{f(n)}{g(n)}\right\| = 0$	∀M > 0, ∃x₀ such that \|f(x)\| < M\|g(x)\| for all x > x₀.
$f(n) \in \omega(g(n))$	漸近支配的	$\lim_{n \to \infty} \left\|\frac{f(n)}{g(n)}\right\| = \infty$	∀M > 0, ∃x₀ such that \|f(x)\| > M\|g(x)\| for all x > x₀.

ここでの記号 o はギリシャ文字のオミクロンである^[1]が、「小文字のオー」と呼ぶこともしばしばである。

f(n) = o(g(n)) であるという関係を、「f(n) はスモール・オーのオーダーで g(n)」などという。これは直感的には、g(n) は f(n) よりもずっと早く発散するということを意味している。もちろん数学的に厳密に言えば、f(n)/g(n) が極限で 0 へ行くという意味である。例えば、

$2 n = o (n 2),$
$2n^2 \ne o(n^2)$

などとなる。Θ-記法と Ω-記法は計算幾何学でよく用いられる記法であり、ο-記法は数学ではよく目にするが計算幾何学ではそれほどは見かけない。ω-記法を用いるのは稀である。

また、計算幾何学では Õ を

$f(n) = \tilde{O} (g(n))$

がある k について f(n) = O(g(n)log_k(g(n))) となることとして用いる。対数因子を無視すればこれは本質的には O-記法である。この記法は "nit-picking" のクラスを記述するのにしばしば用いられる。これは log_k(n) が任意の定数 k と正の定数 ε に対して常に ο(n^ε) となるからである。

以下の性質も重要である。

$o(f) + o(f) \subseteq o(f)$
$o(f)o(g) \subseteq o(fg)$
$o(o(f)) \subseteq o(f)$
$o(f) \subset O(f)$

[編集] 多変数の場合

漸近記法は多変数になっても有効である。たとえば

$f(n,m) = n^2 + m^3 + \hbox{O}(n+m) \mbox{ as } n,m\to\infty$

という言及が示唆するのは、定数 C, N で

$\forall n, m>N: |g(n,m)| \le C(n+m).$

を満たすものの存在である。ここで g(n,m) は

f (n, m) = n 2 + m 3 + g (n, m)

で定められるものである。混乱を避けるためには、動かす変数は常に明示する必要がある。つまり

$f(n,m) = \hbox{O}(n^m) \mbox{ as } n,m\to\infty$

という言明は、次の

$\forall m: f(n,m) = \hbox{O}(n^m) \mbox{ as } n\to\infty.$

とは明確に異なる言明である。

[編集] 一般化と関連用法

関数のとりうる値は、絶対値をノルムに取り替えるだけでそのまま任意のノルム線型空間の元に一般化できる。f や g は同じ空間に値を取る必要はない。g のとる値は任意の位相群の元にすることも可能である。

「極限操作」"x → x₀" は、勝手なフィルター基の導入によって f と g の有向点族として一般化される。

o-記法は微分の定義や、極めて一般の空間における微分可能性を定義するのに有効である。また、関数の漸近同値を

$f\sim g \iff (f-g) = o(g)$

と定めることができる。これは同値関係であり、上述の f が Θ(g) 程度であるという関係よりもなお強い制限を表す記法になっている。f と g が正値実数値関数なら lim f/g = 1 なる関係式に簡略化できる。例えば、2x は Θ(x) のオーダーだが、 2x − x は o(x) のオーダーでない。

[編集] 関連項目

漸近展開: テーラーの公式の一般化である関数の近似
漸近最適: A phrase frequently used to describe an algorithm that has an upper bound asymptotically within a constant of a lower bound for the problem
ハーディー記法: 別の漸近記法
Nachbin's theorem: a precise way of bounding complex analytic functions so that the domain of convergence of integral transforms can be stated.

[編集] 参考文献

Marian Slodicka & Sandy Van Wontergem. Mathematical Analysis I. University of Ghent, 2004.
Donald Knuth. Big Omicron and big Omega and big Theta, ACM SIGACT News, Volume 8, Issue 2, 1976.
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.

翻訳中：この項目「ランダウの記号」は翻訳中です。翻訳作業などに協力して下さる方を求めています。詳細はこの項目のノートや履歴、翻訳FAQなどを参照してください。

"http://ja.wikipedia.org../../../%E3%83%A9/%E3%83%B3/%E3%83%80/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7.html" より作成

カテゴリ: 翻訳中 | 数学の表記法 | 計算複雑性理論 | 数学に関する記事