시간 복잡도 분석과 증명

학습 목표

• 점화식의 개념을 이해하고, 알고리즘 분석에서 점화식의 유용함에 대하여 설명할 수 있다.
• 점화식의 점근적 분석 방법을 이해하고 실제 간단한 점화식에 대하여 점근적 분석 방법을 적용하여 분석할 수 있다.
• 마스터 정리를 이해하고 실제 마스터 정리를 활용하여 주어진 점화식을 분석할 수 있다.

시간 복잡도의 점근적 표기법의 정의 Review

O(g(n)) : f(n) ≤ cg(n) ⇒ g(n) = f(n)의 상한 (upper bound) (이를 만족하는 상수 c가 존재한다)

𝜴(g(n)) : f(n) ≥ cg(n) ⇒ g(n) = f(n)의 하한 (lower bound) (이를 만족하는 상수 c가 존재한다)

𝜣(g(n)) : c2g(n) ≤ f(n) ≤ c1g(n) = f(n)의 상한/하한 (이를 만족하는 상수 c1과 c2가 존재한다)

점화식

• 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한것

• 점화식은 분할 정복 알고리즘, 동적 계획 알고리즘에서 자주 사용됨
• 점화식, 문제를 푸는 방법은 동일함, 하지만 문제의 크기(입력의 크기)가 달라진는 문제에서 주로 사용
• 문제를 표현하는 함수들의 관계를 식으로 정형화 ⇒ 재귀식

• T(n) = 2T(n/2) + n 이 합병 정렬 시간복잡도이다

점화식의 점근적 분석 방법