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

 

 

 

 

---

 

점화식(Recurrence Relation = Recurrence Relation)

• Recurrence : 우리가 아는 자료구조의 리커전의 그 단어가 맞다. 재귀. 재귀적 함수의 복잡도를 구하는 데에 유용하다. 
• 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것이다.
• n번째 항의 값을 n보다 작은 항의 값으로 표현
• 등차수열, 팩토리얼, 피보나치 수열, Merge Sort 등이 있다.

 

재귀적 용법

=> 큰 문제를 푸는데 작은 문제로도 바꿔서 표현이 가능할 때, 또는 작은 문제들을 쭉 풀어왔을 때, 똑같은 포맷으로 풀어왔지만 들어가는 argument, 즉 data 개수 등을 변경해서 모아봤을 때 문제가 풀릴 때 이를 재귀적 용법이라 할 수 있다.

 

 

왜 알고리즘 분석에서 점화식이 중요한가?

• 컴퓨터 자료구조의 대부분이 재귀적 구조
• 재귀적 자료구조 -> 재귀적 알고리즘 -> 점화식으로 시간 복잡도를 표현하게 된다.
• 큰 문제를 작은 동일 문제들로 분해하는 분할정복 패러다임

 

Merge Sort의 점화식 분석

1. 배열을 반으로 나눈다.(분할)
2. 각 반쪽을 재귀적으로 정렬(정복)
3. 정렬된 두 부분을 병합(결합)

 

시간복잡도 점화식

T(n) = 2T(n/2) + O(n)

• 2T(n/2) : 두 개의 반쪽을 각각 정렬하는 시간
• O(n) : 병합하는데 드는 시간(후처리 시간, 오버 헤드)

 

 

 

 

---

반복대치(Iteration Method)

예제 1 / T(n) = T(n-1) + c

 

점화식을 반복적으로 전개하여 패턴을 발견한다.

 

 

 

 

예제 2 / 병합 정렬(T(n) <= 2T(n/2) + n)

 

 

 

 

 

 

---

추정후 증명(Guess & Verification)

식의 모양을 보고 점근적 복잡도를 추정한 후 귀납적으로 증명한다.

1. (경험이나 패턴 관찰을 통해) 결과를 추정
2. 수학적 귀납법(Strong Induction)으로 증명

 

T(n) <= 2T(n/2) + n은 Merge Sort의 점화식이다.

우리가 복잡도를 계산한다고 생각하면 골머리 아파하는 사람들이 있다. 너무 막막하게 생각하지 말자.

앞으로 복잡도를 계산하다보면 생각보다 몇 종류 안된다.

logn / n / nlogn / n^2

대체적으로 이 네 종류로 귀결될 것이기에, 하다보면 대충 어느 정도의 복잡도인지 감이 오게될 것. 계산에 너무 목맬 필요 없다.

 

 

 

 

 

 

 

 

 

 

 

 

---

마스터 정리(Master Theorem)

 

 

직관적 이해

• h(n)이 더 무거우면 h(n)이 지배
• f(n)이 더 무거우면 f(n)이 지배
• 같은 무게면 h(n) * logn

 

 

 

 

 

 

 

 

 

 

---

실무적 관점

점화식 풀이 방법 선택의 기준

• 반복 대치 : 단순한 점화식, 직관적 이해가 필요할 때
• 추정 후 증명 : 결과를 예측할 수 있지만 정확한 증명 필요할 때
• 마스터 정리 : T(n) = aT(n/b) + f(n) 형태일 때 즉시 적용