[알고리즘] 시간복잡도 분할과 정복

분할 정복 알고리즘

분할 정복 알고리즘은 문제를 작은 하위 문제로 분할하고, 각 하위 문제를 재귀적으로 해결한 후, 그 해결책들을 합쳐서 원래 문제의 해결책을 구하는 알고리즘이다.

 

분할 정복의 전형적인 예시로 합병 정렬을 들 수 있는데,

합병 정렬은 배열을 반으로 나누고,

각 반을 정렬한 후에 두 개의 정렬된 반을 합쳐서 전체 배열을 정렬하는 과정을 거친다.

 

분할 정복 알고리즘은 문제를 작은 단위로 쪼개서 해결하기 때문에 대규모 문제를 효과적으로 해결할 수 있는 장점이 있지만 이 알고리즘을 사용할 때에는 문제를 적절하게 분할하고, 재귀적인 해결과 합병 과정을 적절히 구현해야 한다.

 

그렇다면 재귀적인 해결 방법이 뭘까?

재귀적 해결방법에 대한 언급이 많이 나와있으나 나에게 확실히 와닿지 않았다. 그말은 그냥 그런가보다하고 썼던거지 왜 재귀적인 해결방법으로 구현해야하는지 정확히 이해가지 않는다는 뜻

재귀적인 해결방법

간단히 말해서 함수가 자기 자신을 호출하여 문제를 해결하는 방법이다. 즉 주어진 문제를 더 작은 하위 문제로 쪼개어 해결하는데 해당 함수를 반복해서 사용하는 것이다. 이때 재귀 함수는 자기 자신이 호출된 곳으로 돌아갈 때 기본 조건이 충족 하여 종료되도록 설계되어야 한다. 

뭔말? 이라고 생각하시는 분 계실지도 모르겠네요..(혹시 재귀 vs 귀납 아직 헷갈리시는분들 링크 걸어둘게요 https://jinyong-factory.tistory.com/107)

 

합병정렬 알고리즘에서 배열을 정렬하는 과정에서 재귀적으로 문제를 해결하는예를 들어보자.

 

예시) 

배열 (1,3,4,6,2,5) 가 있다고 하자.

1. 분할(Divide)

이때 배열을 반으로 나누면 (1,3,4) (6,2,5) 가 된다. 

2. 정렬(Conquer)

(1,3,4) 를 정렬한다 -> (1,3,4)

(6,2,5) 를 정렬한다 -> (2,5,6)

3. 합병(Merge)

(1,3,4) 와 (2,5,6)을 합병하여 정렬

- (1,2,3,4,5,6) 

 

시간복잡도 구하기

- 분할 단계에서 배열을 반으로 쪼개므로 O(logn) (여기서 왜 logn 인지 이해안가시는분? 충분히 이해해요 다음내용에서 자세히 설명드릴게요 https://jinyong-factory.tistory.com/108)

- 정렬과 합병단계에서 배열 합병시 O(n) 의 시간 소요 (여기서 n은 배열의 크기)

따라서 이를 합치면 전체 시간 복잡도 O(n*logn)

 

먼저, 주여진 배열을 반으로 나누고, 각 반을 정렬하기 위해 동일한 정렬함수를 호출한다.

이 과정에서 배열의 크기가 충분히 작아져 기본조건에 도달할 경우 (예를들어 배열의 크기가 1) 정렬이 끝나면 해당 단계의 결과를 반환하여 이전에 호출된 함수가 결과를 합병하게 된다.