알고리즘 공부<3> - 빅오를 찾는 과정?

 

알고리즘의 분할과 정복 과정

 

이전 공부에서 보면 알고리즘의 분할과 정복 과정을 알아봤다

 

정리 하자면

 

분할 - 현재의 문제와 동일하되 입력의 크기가 더 작은 다수의 부분 문제로 분할한다.

정복 - 부분 문제를 재귀적으로 풀어서 정복한다. 부분 문제의 크기가 충분히 작으면 직접적인 방법으로 푼다.

결합 - 부분 문제의 해를 결합해 원래 문제의 해가 되도록 만든다.

 

이러한 재귀 과정을 '바닥을 쳤다'라고 표현하는 베이스 케이스까지 내려올 때까지 과정을 거친다. 이러한 형태는 이전의 계산된결과를 이용하여 현재 계산을 푼다는 점이 있다.

 

이번에는 이러한 재귀과정을 해결하는 방법에 대해 알아보자.

 

방법에는

 

들이 있다 차례대로 

치환법 - 한계를 추측한 후 그 추측이 옳음을 증명하기 위해 수학적 귀납법을 이용한다.

재귀 트리 방법 - 점화식을 각 노드가 재귀 호출의 해당 레벨에 따른 비용을 나타내도록 트리로 변환하여 점화식을 푼다.  그리고 이를 위해 합의 한계를 구하는 기법을 이용한다. 이후 빅오를 구하게 되면 다시 치환법을 이용해 증명하면 된다.

마스터 방법 - 점화식의 답을 제시해주어 증명하는 방법이다.

마스터방법을 제외한 2가지 방법을 차례대로 알아보자

---

 

1. Substitution method

 

과정은 이러하다

이 방법의 핵심은 guess 이다. 그러다보니 솔루션 중에서도 추측하기 쉬운경우에만 적용이 된다.

앞서 설명했었던 합병정렬에 대한 예를 들어보자

추측 과정을 거친후에 귀납법을 이용해 증명할 것이다.

먼저 basis case의 값이 맞는지 확인을 거친다. 

이후 n<k보다 작은 경우에 맞자고 가정하면

 n= k 일때 맞는것을 증명해 보이면된다.

 

 

 

---

 

2. Recursion-Tree Method

 

Recursion-Tree Method 방식은 Substitution Method 도울수 있으며 좋은 추측을 만들어내기 위한 과정이다. 

여기서 재귀트리는 재귀 호출 계층의 시각적 표현으로 각 노드는 단일 하위 문제의 비용을 나타냅니다.

을 한번 표현해 봅시다. 이 식만으로는 빅오를 추측하기 힘듭니다. 따리서 재귀트리 방식을 사용해봅시다.

 

 

또 이 형태는

 

 

 

 

그럼 이제 이 트리의 빅오를 구해보자 먼저 높이는 

이 된다. 

그리고 마지막 base의 개수는 

 

이 된다

이제 함수 호출의 회숫 즉 총합을 구해보면 된다

수식에서

 

이를 치환법 으로 증명하면 되는것을 볼수 있다.

 

 

 

 

---

 

 

 

 

마지막으로 한가지만 더 살펴 보자

 

이런 형태의 시간 복잡도 함수는 어떻게 나오는지 살펴보자

 

 

단 이 형태는 죄우가 불균형 형태일 꺼다 왜냐하면 n/3 < 2n/3 이므로 왼쪽이 더 빨리 1이 될것이다. 즉

이 된다. 또 여기서 참고로

따라서 

 

이제 빅오를 추측했으니 이를 귀납법으로 증명 하면 된다. 귀납법 증명은 앞서 한것과 같다

 

 

 

첫 시작 base case를 증명해야하는데 앞서 이미 식들로 충분히 베이스케이스는 설명 하였다.

따라서 다음을 증명하면 된다.

 

이는 즉

 

이고

이다 여기서

 

 

오늘은 여기까지 

마스터 방식은 생략하겠습니다.