[알고리즘 분석] 1장. 효율, 분석, 그리고 차수 (6)

1. 차수의 주요 성질

1) $ g(n) \in O(f(n)) \ if \ and \ only \ if \ f(n) \in \Omega (g(n)) $
if and only if: 필요 충분 조건
$ g(n) \in O(f(n)) $ 이 성립하면, $ f(n) \in \Omega (g(n)) $ 도 성립한다. 

2) $ g(n) \in \Theta (f(n)) \ if \ and \ only \ if \ f(n) \in \Theta (g(n)) $
$ g(n) \in \Theta (f(n)) $ 이 성립하면, $ f(n) \in \Theta (g(n)) $ 도 성립한다.

3) b > 1 이고 a > 1 이면, $ log_{a}{b} \in \Theta (log_{b}{n}) $ 은 항상 성립
- 로그 복잡도 함수는 모두 같은 카테고리에 속한다 -> $ \Theta() $ 관계가 성립한다.
- 따라서 로그 복잡도 함수는 $ \Theta(lg\ n) $ 으로 표시한다.

4) b > a > 0 이면, $ a^{n} \in o(b^{n}) $ 이 성립
- 지수 복잡도 함수는 모두 같은 카테고리에 있는 것이 아니다.

5) a > 0 인 모든 a에 대해, $ a^{n} \in o(n!) $ 이 성립
- n!은 어떤 지수 복잡도 함수보다도 나쁘다.

6) 복잡도 함수 나열
$ \Theta(lg\ n), \Theta(n), \Theta(nlg\ n), \Theta(n^{2}), \Theta(n^{j}), \Theta(n^{k}), \Theta(a^{n}), \Theta(b^{n}), \Theta(n!) $
- k > j > 2, b > a > 1
- 이 순서에서 g(n)이 왼쪽, f(n)이 오른쪽이라고 하면, $ g(n) \in o(f(n)) $이 성립한다.

7) $ c \geq 0, d \geq 0, \ g(n) \in O(f(n), \ h(n) \in \Theta(f(n)) $ 이면, $ c \times g(n) + d \times h(n) \in \Theta(f(n)) $
- c * g(n)은 작은 값 -> h의 관계를 따라간다.

 

2. 극한을 이용해 차수 구하기

$ \lim_{n \rightarrow \infty}\frac{g(n)}{f(n)} $ 값이
1) c > 0일 때, $ g(n) \in \Theta(f(n)) $ 
- g(n)과 f(n)은 같은 카테고리에 속한다.
2) = 0 일 때, $ g(n) \in \theta(f(n)), g(n) \in \omega(f(n)) $
- 분모인 f(n)이 더 큰 카테고리에 속한다.
3) $ \infty $ 일 때, $ g(n) \in \omega(f(n)), f(n) \in \theta(f(n)) $
- 분자인 g(n)이 더 큰 카테고리에 속한다.

 

3. 알고리즘 복잡도와 컴퓨터 능력

1. 알고리즘 복잡도 cn이고, t시간 동안 문제크기 m개의 문제를 해결 할 수 있다.
- 기계의 처리 속도가 2배가 된다면 -> t시간 동안 2m개의 문제를 해결 할 수 있다.

2. 알고리즘 복잡도 $ cn^{2} $이고, t시간 동안 문제크기 m개의 문제를 해결 할 수 있다.
- 기계의 처리 속도가 4배가 된다면
- $ 4cm^{2} = c(2m)^{2} $, 2m의 문제를 t시간에 해결할 수 있다.

3. 알고리즘 복잡도 $ c2^{n} $이고, t시간 동안 m개의 문제를 해결 할 수 있다.
- 기계의 처리 속도가 2배가 된다면
- $ 2c2^{m} = c2^{m+1} $ , m+1의 문제를 t시간에 해결할 수 있다.
- 기계의 처리 속도가 100배가 된다면
- $ 100c2^{m} = c2^{m + lg100} $, m + lg100의 문제를 t시간에 해결할 수 있다.