5.4 재귀 알고리즘과 머지소트merge sort 시간복잡도

시작하기에 앞서

특정한 입력값 집합으로 이루어진 문제에 대한 정답은 같은 문제에 대한 작은 입력 값 집합에 대한 정답으로 축소할 수 있습니다. (이것은 부분 문제subproblem 이라는 꽤 중요한 표현입니다.)

예를 들어, 두 양의 정수 a, b의 최대공약수(GCD)를 구하는 문제를 생각해보자. 여기서 b>a. 이 문제는 더 작은 입력값인 b mod a 와 a의 최대공약수를 구하는 문제로 축소될 수 있다.  왜냐하면 gcd(b mod a, a) = gcd(a, b)이기 때문이다.

이런 문제 축소가 수행될 수 있다면, 원 문제의 정답은 이런 축소된 문제의 흐름(좀 더 엄밀하게는 축소된 문제의 나열sequence of reductions) 속에서 찾아 낼 수 있다. 계속 축소하다보면 정답을 정확하게 알 수 있는 최초의 상황을 알게된다. 예를 들어, 최대 공약수를 찾는데, 두번째 숫자가 0일 때까지 계속 문제를 축소 할 수 있다. 왜냐하면 gcd(a, 0) = a (a > 0)이기 때문이다.

이제 원 문제를 작은 입력값을 받는 문제로 축소해서 문제를 재귀적으로 풀어나가는지 다양한 문제를 봐서 풀어볼것이다.

정의

어느 알고리즘이 원 문제를 같은 문제이지만 작은 입력값을 받도록 축소해서 문제를 푸는 것을 재귀 알고리즘이라고 한다. 

예제 1

재귀 알고리즘을 이용해 n! 을 구해보자.

n! = n * (n-1) * (n-2) ... * 1 이다. 여기서 n! 는 n* (n-1)!이다. 따라서 n!을 구하는데 부분문제는 (n-1)!을 구해야하는 것이고, (n-1)!를 구하려면 (n-2)!를 구해야한다. 이를 재귀 함수로 작성해보면 다음과 같다.

예제 3

재귀 알고리즘을 이용하여 두 양의 정수 a, b의 최대공약수를 구해라. 여기서 a< b이다.

우리는 이미 gcd(a, b) = gcd(b mod a, a) 이며, gcd(0, b)=b 임을 알고있다. 여기서 b>0

a= 5, b=8이라고하자. gcd(5,8) = gcd(8 mod 5, 5) = gcd(3, 5) 이다.

gcd(3, 5) = gcd( 5 mod 3, 3 ) = gcd( 2, 3) 이다. 그뒤, gcd(2, 3) = gcd(3 mod 2, 2) = gcd(1, 2) 이다.

그뒤에는, gcd(1, 2) = gcd(2 mod 1, 1) = gcd(0, 1)이다.

따라서, gcd( 5, 8 ) = gcd(0, 1) = 1 이다.

아래는 코딩을 해본것이다.

예제 6

이진 탐색을 재귀 알고리즘으로 설계해보자.

우리가 어떤 수 x를 수열 a1, a2, a3.... an 에서 찾는다고 하자. (여기서 ak 수열은 증가순으로 정렬되어있다.) 이진 탐색을 수행하기 위해서, 우리는 우선 중간항 a [(n+1)/2] (ceiling)과 비교한다. 만약 그 위치의 원소 값과 x가 같으면 그 원소를 반환하면 되고, 크면 1 ~ [(n+1)/2]-1 에서 찾으면 된다. 그렇지 않으면 [(n+1)/2]+1 ~ n 사이에서 찾으면된다. 또 거기서 절반과 비교해서 크면 그 위까지, 작으면 그 아래까지 그 사이에서 x를 찾는다.

이렇게 가능한한 원 문제를 절반의 입력값으로 들고 들어가서 찾는다. 만약 절대 인덱스를찾지 못한다면 -1 을 반환한다.

함수로 작성해보았다.

재귀 알고리즘을 이용한 정렬

Merge Sort 알고리즘이라고 불리는 재귀 정렬 알고리즘을 알아 볼것이다.

merge sort는 원 수열을 부분 수열로 나눈다. 부분수열은 비교할 수 있는 최소의 수열까지 계속해서 부분 수열(부분 문제)로 나뉘어 진다. 나눠지는 모습이 마치 balanced binary tree와 같다. 

이제 이런 절차는 이 나눠진 부분 수열들을 순서대로 합치면서 오름순 또는 내림순으로 정렬한다. 

아래그림은 수열을 비교할 수 있는 최소의 수열까지 계속해서 부분 수열로 나누고, 다시 그것을 오름순으로 정렬하면서 합치는 과정이다.

스도코드는 다음과 같다.

List = { a1, a2, ... an }

divide (List) ={

n = List.Size

if (n>1) {

  m = n/2
  List1 = {a1, a2, ... am}
  List2 = {am+1, am+2, ... an}
  return merge ( divide(List1) , divide(List2) )

}

else return List

}

merge (List1, List2) ={

List = empty List

while (!List1.empty() && !List2.empty()) {

    if( List1.top() > List2.top() ) List.push(List2.pop())
    else List.push(List1.pop())
}
while(!List1.empty()) List.push(List1.pop())
while(!List2.empty()) List.push(List2.pop())

return List

}

정렬된 두 리스트를 비교하면서 합치는데에 비교가 얼마나 발생하는가 추정해볼것이다. 어떤 두 리스트를 비교할 때, 결과적으로 숫자가 작은것이 그 상위 리스트로 합쳐진다. 만약, 두 리스트 중 한개가 비어있다면, 나머지 리스트가 순서대로 통째로 그곳에 복사된다. 왜냐하면 각 리스트들은 정렬되어있기 때문에 비교 후 남은 하나의 리스트를 그대로 상위 리스트에 넣으면 된다.

이러한 비교 작업은 최대 m+n-1 만큼 수행된다.

잘 생각해보면 당연한거다. 

예로 리스트 1개 3개 크기를 상위 리스트로 합칠때, 최대 3번의 비교가가능하다. 최소는 2번이다. 왜냐하면 ceiling [ log 3 ] 이기 때문이다. 선형 탐색말고 이진탐색을 사용하면 그렇다. 
하지만, 각각 m과 n 크기라면 m+n-1 이 제일가능한 비교횟수이다. 즉, m+n-1 보다 더 적게 비교할 수 없다.

merge sort의 수행복잡도를 연산하기 위해, 우선 n개의 원소를 정렬한다고 가정하자. 단, n을 2의 승수로 2^m 이라고 하자. 그래야 분석이 조금 더 쉬워진다.

맨 처음 2개로 분할할 때, 이 2 부분 문제(수열, 리스트)는 2^m-1 개의 원소를 정렬하는 것으로 바뀐다.
그리고 두 번째에는, 각 리스트를 2^(m-2) 개의 원소를 정렬하는 것이 된다. 이렇게 계속된다. 맨 처음 문제에서 트리로 점차 퍼져가며 분할되는 것을 상상해보라. 그림은 아래와 같다..

총 원소가 2^m개일 경우 리스트를 2분할 해갔을때 트리의 단말 노드의 높이가 모두 같게 된다. 

어쨌든 이렇게 다음 레벨로 분할해서 내려가면 결국에는, k 번째에서는 2^(m-k) 개의 부분 수열을 정렬하게 된다. 그래서 결국엔 레벨 m 때, 2^(m-m) 즉, 1개의 부분수열을 정렬하게 되고 이런 것이 총 2^m개가 존재하게된다.

이제 m-1 수준에서, m 수준에 존재하는 각각 원소들을 합칠것이다. 아래의 그림에선, 4 수준에 존재하는 각각의 1개 원소들이 있는데, 3수준에서 처럼 2개로 합칠거다. 이때 오름차순으로 만들기위해 비교연산이 정확히 한번 수행된다.

이런 수행을 계속하게 되면, k 수준에서의 2^k개의 2^(m-k) 길이의 리스트가 2^(k-1)개로 합쳐지게 된다. 이때 길이는 2^(m-k+1)이 된다. 

이때 합쳐질때의 시간복잡도는, 아까전에 서술했듯이, 양 리스트의 크기 를 더하고 거기서 -1 을 한것이다. 즉, k 수준에서의 2^(m-k) 길이의 두 리스트가 합쳐지기 위한 시간복잡도는, 최대의 경우

( 2*2^(m-k)-1 )* 2^(k-1) 이다.

왜냐하면 그렇게 합칠 리스트가 2^(k-1) 개 만큼 있기 때문이다. 

그리고 수준 k가 1~m 까지 수행되므로, 다음과 같이 정리할 수 있다.

이때, 앞의 항은 m*2^m 이며 뒤 항은 2^m -1 이다.(등비수열의 합)

따라서 전체 식을 정리하면 m * 2^m - 2^m +1 이며, 맨 처음 정의한 n = 2^m 을 이용하면

m* 2^m - 2^m +1 = log(2) n * n - n + 1 임을 알 수 있다.

일반화 한 함수를 적으면

T(n) = 2T(n/2) + n 이라고 할 수있다. 우측 항의 T(n/2)는 재귀함수를 뜻하며, n의 복잡도는 n크기만큼의 배열을 정리하는데에 사용된다. 위에서 n/2+n/2-1 과 같은논리다. 다만 여기서는 비교수행도가 아닌 전체적인 복사 수행시간이다. 따라서, 

T(n) = 2T(n/2) + n 는, 정확히 log(2) n 만큼 반복되며,

함수를 풀어보면, 2^(log (2) n) + n*log(2)n 임을 알수있다. *2, +n 은 log(2) n 만큼 반복된다.

따라서, T(n) = n + n log (2) n 이며 Big - O notation에 따라. O(T(n)) = n log n 이 된다.

끄읕~

참고: 머지소트 구현 merge sort implementation

https://www.geeksforgeeks.org/merge-sort/