[자료구조] #2 알고리즘 분석(2)

1. Big-O Notation

함수의 증가율에 대한 상한

수학적 정의

 

Big-O Notaion은 Worst Case에 대한 상한을 제시하여 주어진 입력 크기에 대해 알고리즘이 Big-O로 표현된 함수보다 더 나빠질 수 없다는 것을 의미한다.

즉, 우리가 관심있는 시간복잡도가 Big-O 집합 안에 속해야 한다.
(작게 수행되어야 한다.)

 

정의를 이용해서 어떤 시간복잡도가 Big-O에 속하는 것을 증명하는 문제가 자주 출제되는데, 이때 우리는 상수C와 n0를 찾아야 한다.

 

예를 들어 T(n) = 5n²이고 이때 T(n) ∈ O(n²)이라면, C(T(n)의 상수라고 가정)는 6, n0는 1이 되어야 한다.(여러 정답중 1개)

 

Basic Operation에서 n0가 1일때 보통 '상수시간 걸린다' 라고 한다. 

 

• Tight Bound & Loose Bound

 

T(n) = 2n + 3일때, 시간복잡도 O(n), O(n²), O(n³),  O(n⁴)가 있다면 O(n)은 tight하고 나머지 세개는 loose한 것이라고 할 수 있다. 

 

성능을 비교하기 위해서는 가능한 tight하게 비교해야 한다. 

 

2. Big-Omega Notation

함수의 증가율에 대한 하한

 

Big-Omega Notation은 반대로 Best Case에 대한 상한을 제시하여 최선의 상황을 보여준다.

 

따라서 Big-Omega만 가지고 성능 비교를 하는 것은 불가능하다.

 

3. Big-Theta Notation

점근적으로 tight한 Bound

수학적 정의

 

Upper Bound와 Lower Bound가 아닌 tight한 Bound를 구하는 방법이다. 

 

예를 들어 T(n)이 5n²이고 T(n) ∈ O(n²)이라면, 5n² ∈ O(n²) 이고 5n² ∈ Ω(n²)이기 때문에 n²은 둘 다 만족한다고 할 수 있다.

 

알고리즘 성능 비교표

 

• 시간복잡도를 편리하게 계산하는 법칙

 

1. If T(n) ∈ O(f(n)) and f(n) ∈ O(g(n)), then T(n) ∈ (g(n))
   
   
2. If T(n) ∈ O(kf(n)) for constant k > 0, then T(n) ∈ O(f(n))
   (k는 무시해도 괜찮다)
   
   
3. If T1(n) ∈ O(f1(n)) and T2(n) ∈ O(f2(n)),
   then T1(n) + T2(n) = (T1 + T2)(n) ∈ O(max(f1(n), f2(n))

// 두 개의 파트로 나눠서 구한다
def main(n): 
  # Part 1
  sum = 0
  for i in range(0, n):
	sum += 0

  # Part 2
  for i in range(0, n):
	  for j in range(0, n):
		sum += 1
// (T1 + T2)(n) ∈ O(max(n, n²)) = O(n²)

   

   4. If T(n) varies by conditions as follows, then take greater complexity
       (제일 큰 것을 취한다.) 

def main(n):
    if some condition:
       do something in O(n)
       
    else:
         do something in O(n²)
// T(n) ∈ O(max(n, n²)) = O(n²)

   

   5. If T1(n) ∈ O(f1(n)) and T2(n) ∈ O(f2(n)),

       then T1(n) * T2(n) ∈ O(f1(n) * f2(n))

for i in range(0, n): // T1(n) ∈ O(n)

    for j in range(0, n):
        sum += 1 // T2(n) ∈ O(n)

// T1(n) * T2(n) ∈ O(n*n) = O(n²)

 

Rlue 5 예외사항

이렇게 추정해도 틀린 것은 아니지만 loose한 형태이다.