Aritalab:Lecture/Algorithm/BigO
From Metabolomics.JP
< Aritalab:Lecture | Algorithm(Difference between revisions)
m |
|||
Line 1: | Line 1: | ||
__FORCETOC__ | __FORCETOC__ | ||
==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 18: | Line 20: | ||
を満たすならば | を満たすならば | ||
: f(x) = Θ(g(x)) | : f(x) = Θ(g(x)) | ||
− | + | と書きます。 | |
==注== | ==注== | ||
O、Ω、Θ記法で表しているのは関数の集合であるため、本当なら | O、Ω、Θ記法で表しているのは関数の集合であるため、本当なら | ||
: f(x) ∈ O(n<sup>n</sup>) | : f(x) ∈ O(n<sup>n</sup>) | ||
− | + | のように書かなくてはなりません。しかし、便宜的に | |
: O(n) + O(n) = O(n)、や | : O(n) + O(n) = O(n)、や | ||
: f(x) = x<sup>2</sup> + O(n) | : f(x) = x<sup>2</sup> + O(n) | ||
− | + | のように書くことが多いです。 | |
+ | また上の定義からは、 | ||
+ | : log n = O(n) | ||
+ | : n = O(n<sup>2</sup>) | ||
+ | なのですが、このような書き方もほとんどせず、O記法をΘのようにみなして書きます。 |
Revision as of 03:07, 8 November 2010
Contents |
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))
と書きます。
注
O、Ω、Θ記法で表しているのは関数の集合であるため、本当なら
- f(x) ∈ O(nn)
のように書かなくてはなりません。しかし、便宜的に
- O(n) + O(n) = O(n)、や
- f(x) = x2 + O(n)
のように書くことが多いです。 また上の定義からは、
- log n = O(n)
- n = O(n2)
なのですが、このような書き方もほとんどせず、O記法をΘのようにみなして書きます。