알고리즘 수행시간을 나타내는 함수

• $\Theta, O, \Omega, o, \omega$ 함수

• 가장 많이 사용하는 함수 - $\Theta, O$

• $\Theta$ 함수

  $\Theta(f(n)) = g(n)$ 이라고 할 때

  • $g(n)$은 $f(n)$과 같은 차수이며 통상적으로 최고차항 하나만으로 정한다.
  • ex : $g(n) = 3n^2 + 2nlog_2n+8 → \Theta(n^2)$

• $O$ 함수

  $O(f(n)) = g(n)$ 이라고 할 때

  • $f(n)$은 $g(n)$보다 차수가 같거나 더 높은 식, 통상적으로 항 하나만 정한다.
  • ex : $g(n) = 3n^2 + 2nlog_2n+8 → O(n^2), O(n^2logn), O(n^3) \cdots$
  • 코드를 보고 유추해내기 편하기 때문에 $O$함수를 사용
  • 최적의 $O$함수를 사용할 것!

Mathematical Background

• 정리1 : $g(x) = a_kx^k + a_{k-1}x^{k-1}+ \cdots + a_1x+a_0$ 이라고 하고(단, 최고차항 계수 $a_k > 0$), $l$은 $k$보다 큰 자연수이다. $n>n_0$ 인 모든 자연수 $n$에 대하여 $n^l > g(n)$이 되게 하는 자연수 $n_0$가 존재한다.

  → $n>n_0$ 인 부분부터 $n^l$ 이 $g(n)$보다 빠르게 증가한다

  → 다항식끼리 비교는 차수가 중요하다

  

  • 따름정리1. $f(x)$는 최고차항의 계수가 양수인 다항식이다. 모든 $n>n_0$ 인 자연수 n에 대하여, $f(n) > 0$ 이 되게 하는 자연수 $n_0$가 존재한다.
  • 따름정리2. $f(x)$와 $g(x)$는 다항식으로, 둘다 최고 차항의 계수가 양수이며, $f(x)$의 차수가 $g(x)$의 차수보다 크다. 이 때 $n>n_0$ 인 모든 자연수 $n$에 대하여, $f(n) > g(n)$이 되게하는 자연수 $n_0$가 존재한다.
  • 따름정리3. $f(x)$와 $g(x)$는 같은 차수의 다항식으로, 둘다 최고 차항의 계수는 양수이며, $f(x)$의 최고차항 계수가 $g(x)$의 최고차항 계수보다 클 때, $n>n_0$ 인 모든 자연수 $n$에 대하여, $f(n) > g(n)$이 되게하는 자연수 $n_0$가 존재한다.

• 정리2. 임의의 최고차항 계수가 양수이면서, 상수가 아닌 다항식 $f(x)$가 있다. $n>n_0$ 인 모든 자연수 $n$에 대하여, $f(n) > logn$ 이 되게하는 자연수 $n_0$가 존재한다.

  • 예비정리 : 임의의 양의 실수 r에 대하여 x가 무한히 커짐에 따라 $\frac{logx}{x^r}$은 0에 수렴한다.

    → r이 아무리 작아도 0에 수렴함

  → $f(x)$가 $r(r>0)$차식이고, $x^r$의 계수를 $a_r$이라고 하자. $\frac{f(x)}{x^r}$와 $\frac{logx}{x^r}$는 $x$가 무한히 커질 때, 각각 $a_r, 0$ 으로 수렴한다. 따라서 충분히 큰 자연수 $n_0$에 대하여, $x>n_0$ 일 때, $\frac{f(x)}{x^r} > \frac{logx}{x^r}$ 이 된다.

  → 다항식 vs 로그 이면 무조건 다항식이 빨리 커진다

  

  • 따름정리4. 임의의 최고차항의 계수가 양수이면서, 상수가 아닌 다항식 $f(x)$와 2이상의 자연수 $c$에 대하여, $n>n_0$인 자연수에 대하여, $f(n) > log_cn$이 되게하는 자연수 $n_0$가 존재한다.

    → 양변에를 $log_ec$ 를 곱하면 상수$\times f(n) > logn$ : 성립

$\Theta$ 함수

• 수행시간 $f(n)$과 다항식 $g(n)$에 대하여 $n>n_0$인 모든 자연수 $n$에 대하여 $0≤c_1g(n)≤f(n)≤c_2g(n)$을 만족하는 자연수 $n_0$와 양의 실수 $c_1, c_2$가 존재할 때 $f(n) = \Theta(g(n))$ 이다

  → 차수가 같아야함.

  → 따름 정리3. 같은 차수일 때 최고차항이 더 크면 $f(n)>g(n)$ 이 되게하는 자연수 $n_0$ 존재

• $\Theta$ 함수에 들어가는 식은 다항식의 최고 차항에서 계수를 뺀 부분

• 수행시간이 오래걸리는 순서는 다음과 같다.

  $\cdots > \Theta(2^n) > \Theta(n^3) > \Theta(n^2) > \Theta(n^{1.xxxx \dots}) \newline >\Theta(nlogn)>\Theta(n)>\Theta(n^{0.xxx \dots}) > \Theta(logn)>\Theta(1)$

$O$함수

• 수행시간 $f(n)$과 다항식 $g(n)$에 대하여 $n>n_0$인 모든 자연수 $n$에 대하여 $f(n)≤cg(n)$을 만족하는 자연수 $n_0$와 양의 실수 $c$가 존재할 때 $f(n) = O(g(n))$ 이다

  → 차수가 같아야함

  → 수행시간의 상한을 나타낸다. 알고리즘 최악의 경우의 수행시간을 구할 떄 사용

  → 상한선은 최소로 잡아야 수행시간을 파악하기 좋으므로 차수는 가능한 최소(같음)로 잡는다.

$\Omega$ 함수