2. 점화식과 알고리즘 복잡도 분석

점화식

점화식이란?

• 어떤 함수를 자신과 똑같은 함수를 이용해 나타내는 것

점화식의 점근적 분석 방법

• 반복 대치 : 반복해서 집어 넣는다.

• 추정 후 증명 : 추정 후 경계 조건 + 귀납적 가정과 전개를 이용해 증명한다. 이때 잘못 증명하지 않도록 주의해야 한다.
  • 예시  
    • 추정 : $T(n) \le 2T({n \over 2}) + n$ 의 점근적 복잡도는 $T(n) = O(nlogn)$이다. 즉, 충분히 큰 $n$에 대하여 $T(n) \le\ cnlogn$인 양의 상수 $c$가 존재한다.
    • 증명  : 
      • 경계 조건 : $T(2) \le c2log2$인 $c$가 존재  <------필수!
      • 귀납적 가정과 전개 : $ n \over 2 $에 대해 추정이 맞으면, 즉 $T({n \over 2}) \le c{n \over 2}log{n \over 2}$ 이라면 $T(n) \le 2T({n \over 2}) + n \\ \le 2c({n \over 2})log{n \over 2} + n = cnlogn - cnlog2 + n \\ = cnlogn + n(1-clog2) \le cnlogn $ $( c \ge {1 \over log2} )$

• 마스터 정리 : $ T(n) = aT(\frac{n}{b} ) + f(n) $ 꼴을 가진 재귀식에 적용된다. 이때 $ a, b, f(n) $은 알고 있다.

실제 정의

근사 버전