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...) |
|||
| (3 intermediate revisions by one user not shown) | |||
| Line 1: | Line 1: | ||
| + | __FORCETOC__ | ||
| + | ==まとめ== | ||
| + | * O記法は関数の上限を与える | ||
| + | : e.g. log ''n'' = O(''n'' ) | ||
| + | * Ω記法は関数の下限を与える | ||
| + | : e.g. ''n''<sup>2</sup> = Ω(''n'' ) | ||
| + | * Θ記法はO記法とΩ記法をあわせたもの | ||
==O記法== | ==O記法== | ||
| − | ;定義 | + | ;定義 |
関数 f(x) が正の定数 c と適当な値 x<sub>0</sub> に対して | 関数 f(x) が正の定数 c と適当な値 x<sub>0</sub> に対して | ||
: f(x) ≤ c g(x) (∀ x ≥ x<sub>0</sub>) | : f(x) ≤ c g(x) (∀ x ≥ x<sub>0</sub>) | ||
を満たすならば | を満たすならば | ||
: f(x) = O(g(x)) | : f(x) = O(g(x)) | ||
| − | + | と書きます。つまり、O記法は関数の上限を与えます。 | |
| − | + | ==Ω記法== | |
| + | ;定義 | ||
関数 f(x) が正の定数 c と適当な値 x<sub>0</sub> に対して | 関数 f(x) が正の定数 c と適当な値 x<sub>0</sub> に対して | ||
: f(x) ≥ c g(x) (∀ x ≥ x<sub>0</sub>) | : f(x) ≥ c g(x) (∀ x ≥ x<sub>0</sub>) | ||
を満たすならば | を満たすならば | ||
: f(x) = Ω(g(x)) | : f(x) = Ω(g(x)) | ||
| − | + | と書きます。つまり、Ω記法は関数の下限を与えます。 | |
| + | ==Θ記法== | ||
;定義 Θ( ) | ;定義 Θ( ) | ||
関数 f(x) が | 関数 f(x) が | ||
| Line 17: | Line 26: | ||
を満たすならば | を満たすならば | ||
: 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) | ||
| + | のように書くことが多いです。 | ||
| + | また上の定義からは、 | ||
| + | : log n = O(n) | ||
| + | : n = O(n<sup>2</sup>) | ||
| + | なのですが、このような書き方もほとんどせず、O記法をΘのようにみなして書きます。 | ||
Latest revision as of 00:32, 2 June 2011
Contents |
[edit] まとめ
- O記法は関数の上限を与える
- e.g. log n = O(n )
- Ω記法は関数の下限を与える
- e.g. n2 = Ω(n )
- Θ記法はO記法とΩ記法をあわせたもの
[edit] O記法
- 定義
関数 f(x) が正の定数 c と適当な値 x0 に対して
- f(x) ≤ c g(x) (∀ x ≥ x0)
を満たすならば
- f(x) = O(g(x))
と書きます。つまり、O記法は関数の上限を与えます。
[edit] Ω記法
- 定義
関数 f(x) が正の定数 c と適当な値 x0 に対して
- f(x) ≥ c g(x) (∀ x ≥ x0)
を満たすならば
- f(x) = Ω(g(x))
と書きます。つまり、Ω記法は関数の下限を与えます。
[edit] Θ記法
- 定義 Θ( )
関数 f(x) が
- f(x) = O(g(x)), f(x) = Ω(g(x))
を満たすならば
- f(x) = Θ(g(x))
と書きます。
[edit] 注
Ｏ、Ω、Θ記法で表しているのは関数の集合であるため、本当なら
- f(x) ∈ O(nn)
のように書かなくてはなりません。しかし、便宜的に
- O(n) + O(n) = O(n)、や
- f(x) = x2 + O(n)
のように書くことが多いです。 また上の定義からは、
- log n = O(n)
- n = O(n2)
なのですが、このような書き方もほとんどせず、O記法をΘのようにみなして書きます。
