Algorithm : efficiency, analysis and order

차수(Order)

복잡도 함수 표기법

• asymptotic
  • 점근적
  • $f(n)$ 의 asymptotic behavior는 n이 큰 수가 될 때의 $f(n)$이 갖는 특성
  • ex) $f(n) = \frac{1}{n}$ 일 때 $\lim_{n\to\infty} \frac{1}{n} = 0$

1. Big O notation -> $O()$

• asymptotic upper bound (점근적 상한)
• 정의: 주어진 복잡도 함수 $f(n)$에 대하여 $g(n)\in O(f(n))$ 이면 $n\ge N$인 모든 정수 $n$에 대하여 $0 \le g(n) \le c \times f(n)$ 이 성립하는 양의 실수 $c$와 음이 아닌 정수 $N$이 존재한다.
• 입력의 크기 $n$에 대해서 해당 함수를 사용하는 알고리즘의 수행시간은 아무리 늦어도 $cf(n)$이 된다. -> $cf(n)$ 보다 절대로 느릴 수 없다.
• ex1) $n^2 + 10n \in O(n^2)$ 성립 ($c=2, N=10)$ 인 경우
  ex2) $n^3 \in O(n^2)$ 은 성립하지 않음

2. Omega notation -> $\Omega()$

• asymptotic lower bound (점근적 하한)
• 정의: 주어진 복잡도 함수 $f(n)$에 대하여 $g(n)\in O(f(n))$ 이면 $n \ge N$인 모든 정수 $n$에 대하여 $g(n) \ge c \times f(n) \ge 0$ 이 성립하는 양의 실수 $c$와 음이 아닌 정수 $N$이 존재한다.
• 입력의 크기 $n$에 대해서 해당 함수를 사용하는 알고리즘의 수행시간은 아무리 빨라도 $cf(n)$ 밖에 되지 않는다. -> $cf(n)$보다 절대로 더 빠를 수 없다.
• ex1) $n^2 + 10n \in \Omega(n^2)$ 성립 ($c=1, N=0$) 인 경우

3. Theta notation -> $\Theta()$

• asymptotic tight bound
• 정의: 주어진 복잡도 함수 $f(n)$에 대해서 $\Theta(f(n)) = O(f(n)) \cap \Omega(f(n))$
  $n \ge N$인 모든 정수 $n$에 대하여 $c \times f(n) \le g(n) \le d \times f(n)$ 이 성립하는 양의 실수 $c$와 $d$, 음이 아닌 정수 $N$이 존재한다.
• Omega와 Big O를 둘 다 만족하는 것
  ex) $T(n)=\frac{n(n-1)}{2}$ : $O(n^2)$ 이면서, $\Omega(n^2)$이다.
  -> 따라서 $\Theta(n^2)$이다.

4. Small O notation -> $o()$

• upper bound that is not asymptotically tight
• 복잡도 함수 끼리의 관계를 나타내기 위한 표기법
• 정의: 주어진 복잡도 함수 $f(n)$에 대하여 $g(n) \in o(f(n))$ 이면 모든 양의 실수 $c$에 대해, $n \ge N$인 모든 $n$에 대해서 $0 \le g(n) \le c \times f(n))$ 이 성립하는 음이 아닌 정수 $N$이 존재한다.
• Big O랑 같지만 다른 점은 모든 양의 실수 $c$에 대해 성립한다는 점!
• $g(n) \in o(f(n))$ 은 $g(n)$이 $cf(n)$보다 훨씬 낫다는 의미
• ex1) $n \in o(n^2)$ 성립($n>10000$)인 경우
  ex2) $n \in o(5n)$ 성립하지 않음

5. Small Omega notation -> $\omega()$

• lower bound that is not asymptotically tight

Big O VS Small O

• Big O: 실수 $c>0$ 중에서 하나만 성립해도 된다.
• Small O: 모든 실수 $c>0$에 대해서 성립해야 한다.

복잡도 함수 순서 나열

$k>j>2$이고, $b>a>1$ 일때
$\Theta(logn)$, $\Theta(n)$, $\Theta(nlogn)$, $\Theta(n^2)$, $\Theta(n^j)$, $\Theta(n^k)$, $\Theta(a^n)$, $\Theta(b^n)$, $\Theta(n!)$

• 이때 $g(n)$이 $f(n)$보다 왼쪽에 존재하면, 무조건 $g(n)\in o(f(n))$이다.
• $c\ge 0,\ d>0$, $g(n)\in O(f(n))$ and $h(n)\in \Theta(f(n))$이면,
  $c\times g(n) + d\times h(n)\in\Theta(f(n))$

극한 이용하여 차수 구하기

로피탈 법칙

$lim_{n \to \infty}\frac{g(n)}{f(n)}=lim_{n \to \infty}(\frac{g'(n)}{f'(n)})$