알고리즘 공부 <2> - 빅오? 오메가? 세타? 점근적?

1. 알고리즘의 점근적 효율성

알고리즘의 효율성에 대해 체크 할때는 충분히 큰 입력들에 대한 수행시간 증가에 있어 가장 큰 차수만 중요하게 취급한다.

즉, 입력 크기가 극한으로 증가할 때 어떤 알고리즘의 수행시간이 어떻게 증가하는지에 관심을 가진다. 이를 점근 표기법 이라고 한다

2. 빅오 - O 

g(n)은 f(n)에 대한 상한을 뜻한다. 즉 , 시간 복잡도가 최악의 경우더라도 f(n)의 계산 복잡도는 g(n)과 같거나 작다는 것인데  여기서 조건이 있다. 

빅오 O(g(n))에 있어  0 ≤ f(n) ≤cg(n) for all n>n0 을성립해야 한다. 여기서 C는 양의 상수이며 n0는 1 이상 자연수 이어야한다.

간단한 예를 들면

f(n)=n2 - 2n

g(n)=n2

0≤ n2 - 2n ≤cn2 (n>n0)

여기서 c와n0 가 존재 하는지 보여주면된다.

c=3이라고 하면 0≤ n2 - 2n ≤3n2 이고 (n≥n0=2)일때 성립하므로

n2 - 2n = O(n2)  즉 n2 - 2n 은 O(n2)의 속한다고(집합) 할수있다.

또 n2 - 2n =O(n3) 라고도 할 수 있지만 오차(그림)가 더 커지므로 n2 - 2n = O(n2) 라고 한다

---

3. 오메가 - W 

g(n)은 f(n)에 대한 하한을 나탄다. 즉 f(n)의 시간 복잡도가 최선이어도 g(n)보다 크다는 것을 말한다.  여기서 조건이 있다.

오메가 W(g(n))에 있어  0 ≤ cg(n)≤f(n) for all n≥n0 을성립해야 한다. 여기서 C는 양의 상수이며 n0는 1 이상 자연수 이어야한다.

n2 - 2n = W (n2) 대한 예로 c=1/10 과 n0 = 3 일때 만족하므로 한번 해본다(귀찮)

---

4.세타 - Q

이를 점근적 엄밀한 한계 라고 하는데

세타는 간단하게

 f(n) = O(g(n) 

 f(n) = W(g(n)) 이면

 f(n) = Q(g(n)) 이다.

이상 오늘은 빅오 오메가 세타 점근적에 대해서 정리해 보았다.