알고리즘 평가 척도

1. Algorithm's Efficiency

• Time efficiency - 시간복잡도
• Space efficiency - 공간복잡도
  • 사실 이제 공간복잡도는 그렇게 큰 문제는 아님. 메모리 기술이 워낙 좋아져서 이제는 시간복잡도가 거의 유일한 이슈...
    
    

2. Measuring Running Time

• 실제 프로그램 실행 시간을 측정하는 방식
  • 단순하게 프로그램 실행시간을 초/밀리초 등으로 측정

• 시간 측정의 장애 요소
  • 각 컴퓨터마다 다른 실행 속도
  • 프로그램과 컴파일러 등의 성능
  • 프로그램의 실행시간을 정확하게 정의하기 어려움
  • 프로그램의 실행시간만으로 알고리즘의 시간복잡도를 평가하기도 애매함

• 기본적인 연산의 횟수를 세는 방식
  • 알고리즘의 핵심 기능에 해당되는 기본 연산들만을 고려
  • 주로, 반복문 안에서의 연산이 중요!
  • 예를 들면, 정렬 문제에서는 키값 비교 연산, 계산 문제에서는 사칙 연산 등의 횟수를 세는 것

• 프로그램 실행 시간과 기본 연산 횟수 사이의 관계!

  

  • 다음 그림에서 시간복잡도 $T(n)$은 기본 연산 실행 시간 $c_{op}$ 와 기본 연산 실행 횟수 $C(n)$를 곱한 값에 근사한다.
    
    
  • $n$은 Input Size로 이 값이 커질 수록 시간복잡도가 얼마나 커지는지 고려하여 시간복잡도를 계산할 수 있다.
    
    
  • 최종적으로, 작은 $n$ 값에 대하여 실제 실행 시간은 알고리즘의 효율성을 따지는데 그렇게 유의미한 척도가 아니므로, $n$ 이 증가할 수록 실제 실행 시간에 유의미하게 영향을 끼치는 것이 무엇인지 고려해보자.
    
    
  • 그것은 바로 기본 연산의 횟수!!
    
    

3. Order of Growth

• Input size $n$에 대한 Function's order of growth

  

  • 지수 형태의 시간복잡도는 아주 작은 Input에 대해서만 실행가능하다.
  • 경우에 따라서는 Input size 뿐만 아니라, 특정 Input에 대해서 복잡도가 올라가는 경우도 가능하다. (예를 들면, 순차 탐색)
    
    

4. Time Efficiency의 분류

• The Worst-case efficiency - 최악의 경우 시간복잡도
• The Best-case efficiency - 최선의 경우 시간복잡도
• The Average-case efficiency - 평균 시간복잡도
  
  

5. Asymptotic order of growth

• $O(g(n))$ - $g(n)$ 이하의 order of growth function 집합
• $\Omega(g(n))$ - $g(n)$ 이상의 order of growth function 집합
• $\Theta(g(n))$ - $g(n)$과 동일한 order of growth function 집합

g(n)은 실제 기본 연산 횟수에 대한 식
위의 방식에 낮은 차수의 항과 상수항은 무시하고 최대 차수 항의 차수로만 비교

• Prove $O$-notation and $\Theta$-notation

  • $O$-notation : 최고 차항이 동일한 함수 중에 최고차항만 가지는 함수와 대소 비교하여 해당 함수가 작음을 보이면 됨.
    
    
  • $\Theta$-notation : 최고 차항이 동일하고 그 항만을 가지는 함수 사이에 해당 함수가 있음을 보이면 됨.
    
    
  • Using $Limits$