Aritalab:Lecture/Algorithm/BigO
From Metabolomics.JP
< Aritalab:Lecture | Algorithm(Difference between revisions)
(New page: ==O記法== ;定義 O( ) 関数 f(x) が正の定数 c と適当な値 x<sub>0</sub> に対して : f(x) ≤ c g(x) (∀ x ≥ x<sub>0</sub>) を満たすならば : f(x) = O...) |
|||
| Line 1: | Line 1: | ||
| + | __FORCETOC__ | ||
==O記法== | ==O記法== | ||
;定義 O( ) | ;定義 O( ) | ||
| Line 18: | Line 19: | ||
: f(x) = Θ(g(x)) | : f(x) = Θ(g(x)) | ||
と書く。 | と書く。 | ||
| + | |||
| + | ==注== | ||
| + | Ｏ、Ω、Θ記法で表しているのは関数の集合であるため、本当なら | ||
| + | : f(x) ∈ O(n<sup>n</sup>) | ||
| + | のように書かなくてはならない。しかし、便宜的に | ||
| + | : O(n) + O(n) = O(n)、や | ||
| + | : f(x) = x<sup>2</sup> + O(n) | ||
| + | のように書くことが多い。 | ||
Revision as of 14:28, 18 October 2010
Contents |
O記法
- 定義 O( )
関数 f(x) が正の定数 c と適当な値 x0 に対して
- f(x) ≤ c g(x) (∀ x ≥ x0)
を満たすならば
- f(x) = O(g(x))
と書く。つまり、O記法は関数の上限を与える。
- 定義 Ω( )
関数 f(x) が正の定数 c と適当な値 x0 に対して
- f(x) ≥ c g(x) (∀ x ≥ x0)
を満たすならば
- f(x) = Ω(g(x))
と書く。つまり、Ω記法は関数の加減を与える。
- 定義 Θ( )
関数 f(x) が
- f(x) = O(g(x)), f(x) = Ω(g(x))
を満たすならば
- f(x) = Θ(g(x))
と書く。
注
Ｏ、Ω、Θ記法で表しているのは関数の集合であるため、本当なら
- f(x) ∈ O(nn)
のように書かなくてはならない。しかし、便宜的に
- O(n) + O(n) = O(n)、や
- f(x) = x2 + O(n)
のように書くことが多い。
