漸近記法

入力サイズが小さい時よりも、大きい時の増加率を知りたい
- "極限において入力サイズの増加に伴ってアルゴリズムの実行時間が増加する程度に関心がある"
最悪時だけでなく、全ての入力に対して有用な表現が欲しい
- 漸近記法が適している
Θ(g(n)) ={f(n):∃c1,c2,n0∈N, 0 ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n)}
- f(n) : 全 n ≥ n0 に対して0 ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n) を満たす自然数c1,c2,n0 が存在する
- 例:の場合
  - 全てのn>n0に対して $c_1n^2 \le \frac{1}{2}n^2-3n \le c_2n^2$
  - 全辺をで割ると
    - $c_2=\frac{1}{2}$ が $n \geq 1$ で成立
    - $c_1 \le \frac{1}{14}$ が $n \geq 7$ で成立
  - 上記より $c_1=\frac{1}{14},c_2=\frac{1}{2},n_0=7$ が $Θ(n^2)=\frac{1}{2}n^2-3n$ に存在。
- 上記定義でも示すことができる
  - 右辺のみで示せる: $6n^3 \le c_2n^2$
  - n²で両辺を割ると
    - $c_2$ は定数なのでこの不等式を満足しない十分に大きいnが存在する
O記法(O-notation)
- 上界にしか関心がないときはO記法を用いる
  - 漸近的上界
- Θ記法は上界、下界双方に関心があるときに利用する
  - O(g(n)) = {f (n) : ∃ c, n0，∀n (n ≥ n0) , 0 ≤ f(n) ≤ cg(n) }
- Θ(g(n)) ⊆ O(g(n))
- 任意のa>0の二次関数 $an^2 + bn + c∈Θ(n^2)⊂O(n^2)$
- 注意:意外なことに任意の
  - 例:g(n)=4n+5∈O(n²)
  - c=a+|b|,n0 =max(1,−b/a)
    - c=9,n0=1
    - 0 ≤ 4n+5 ≤ 9*n^2
  - タイトな限界ではない。
    - タイトな上界を示す記法をo(n)とする(little-o notation)
      - "o(g(n)) = {f(n): 任意の正の定数c> 0 に対して，ある正の定数 n0 > 0 が存在して，すべての n ≥ n0 に対して 0 ≤ f(n) <cg(n) を満たす}"
  - 漸近的上界と漸近的にタイトな限界は区別するのがアルゴリズム分野の標準
Ω記法
- 下界にしか関心がないときはΩ記法を用いる
- こちらもO記法と同じくタイトな下界ではない。
  - タイトな下界を示す記法をω(n)とする(little omega notation)
    - "ω(g(n)) = {f(n): 任意の正の定数c> 0 に対して，ある正の定数 n0 > 0 が存在して，すべての n ≥ n0 に対して 0 ≤ cg(n) <f(n) を満たす}"
定義比較メモ
- O(g(n)) = {f(n): ある正の定数 c, n0 が存在して，すべての n ≥ n0 に対して 0 ≤ f(n) ≤ cg(n) を満たす}
- Ω(g(n)) = {f(n): ある正の定数 c, n0 が存在して，すべての n ≥ n0 に対して 0 ≤ cg(n) ≤ f(n) を満たす}
- o(g(n)) = {f(n): 任意の正の定数c> 0 に対して，ある正の定数 n0 > 0 が存在して，すべての n ≥ n0 に対して 0 ≤ f(n) <cg(n) を満たす}
- ω(g(n)) = {f(n): 任意の正の定数c> 0 に対して，ある正の定数 n0 > 0 が存在して，すべての n ≥ n0 に対して 0 ≤ cg(n) <f(n) を満たす}