O記法
Landau symbol
関数を上から評価する
関数$ T(n) はたかだか$ n のオーダー
$ T(n) = O(n)
ある自然数$ \Bbb{N} と正の数$ C が存在して、$ N 以上のすべての整数$ n について:
$ |T(n)| \leq Cn
$ \exist N \isin \Bbb{N}, \exist C \gt 0 \quad s.t. \quad \forall n\geq N \implies |T(n)| \leq Cn
オーダー: order of growth
関数を見る道具にできる
関数を抑えて評価する
$ n を定数とすれば、定数で抑えているのと同じ
$ O(\log{n})
$ O(n\log{n})
下から評価する
Ω記法
少なくとも