많은 알고리즘은 큰 문제를 작은 문제로 쪼개서 해결하는 방법으로 해결할 수 있다. 이러한 문제 해결 방법을 Divide and Conquer (분할 후 정복) 이라고도 하는데, 이러한 구조 때문에 알고리즘의 시간 복잡도를 점화식의 꼴로 나타낼 수 있게 된다. 점화식이란 어떤 함수를 그 함수로 나타낸 식을 의미한다. 예를 들면 T(n) = T(n-1) + n 과 같이 T(n)에 대한 정의를 T(n-1)을 이용해 나타낸 경우가 점화식에 해당한다. 이러한 특성을 가진 알고리즘들은 재귀함수와도 연관이 깊다.
이제 시간복잡도가 점화식 꼴로 나타나는 경우 시간 복잡도를 계산하는 방법 3가지를 알아보겠다.
1. 반복대치
첫 번째는 반복대치이다. 반복대치는 처음의 점화식을 계속 대입하면서 시간복잡도를 계산하는 방식이다. 아래의 예를 살펴보자. 다음 게시글에 정리할 merge sort의 시간복잡도는 T(n)<=2T(n/2)+n 의 구조를 띤다.
이는 충분히 큰 n에 대해 성립하는 것이므로 n 대신에 n/2를 넣어도 문제되지 않는다. 따라서 T(n/2) 자리에 n/2를 대입하여 만든 새로운 점화식을 대입하여 대소 관계를 유지하며 식을 전개해나가는 것이다 (1).
이러한 과정을 계속 반복하다보면 (2) 규칙성이 나타나는데, 이를 어떤 상수 k에 대해 나타낼 수 있게 된다 (3).
여기서 2^k = n이라고 하면 (4)와 같이 n에 관한 식을 정리할 수 있고, merge sort의 알고리즘에 따라 T(1) = 1 (또는 양의 상수) 이므로 T(n)<=n+ n*logn이라는 것을 알 수 있고, 따라서 O(n*logn) 알고리즘임을 알 수 있다.
여기서 2^k = n이라는 가정이 이해가 되지 않을 수 있는데, 2^k가 충분히 큰 상수이므로 n이라고 가정해도 일반성이 무너지지 않는다고 생각하면 된다. 이에 대한 수학적인 증명은 게시글 맨 아래에 추가로 첨부했다.
2. 추정 후 증명
추정 후 증명은 말 그대로 T(n)의 시간 복잡도를 예측한 뒤 그게 맞는지 증명하는 과정이다. 증명과정은 문제 상황에 따라 다르겠지만 귀납증명 방식을 주로 사용하는 듯하다. 이번에도 merge sort의 예시를 살펴보면서 정리해보겠다. 우선 우리는 merge sort의 시간복잡도가 O(nlogn)을 따를 것이라고 가정했다. 이는 O(n*logn)의 수학적 정의에 따라 충분히 큰 n에 대해 T(n)<=c*n*logn인 양의 상수 c가 존재한다고 가정한 것과 동치이다. 이제 이 가정을 귀납법으로 증명하면 된다.
귀납증명의 원리는
1. 특정 k 단계 (경계조건) 에서 가정이 성립됨을 증명한 뒤,
2. n-1단계의 특정 조건에서 가정이 성립된다고 가정했을 때 n단계 역시 가정이 성립한다는 것을 증명함
으로써 도미노처럼 k 이상의 모든 n 단계에서 가정이 성립함을 증명하는 것이다.
merge sort의 시간복잡도를 귀납적으로 증명해보자. 우선 경계조건은 아무거나 잡아도 상관없으나 n=1인 경우에는 logn이 0이 되므로 T(n)<=0 이 되어 조건을 만족하지 못하므로 (시간복잡도는 양수) n=2인 경우를 잡았다. 이 경우 c를 적당히 큰 상수로 잡으면 당연히 만족하게 된다. 그리고 여기서 일반적으로 T(n)=O(f(n))임을 증명하는 상황이라면 경계조건(n=k)을 잡았을 때 T(n)과 f(n) 모두 상수가 되기 때문에 적당히 큰 양의 상수 c를 잡으면 T(k)<=cf(k)가 당연히 성립하기 때문에 추정 후 증명과정에서 경계조건 증명은 생략해도 된다고 한다.
귀납적 가정을 통해 이전 단계가 식을 만족할 때, 다음 단계도 식을 만족함을 보이자. 위에서 귀납증명에 대해 설명할 때 편의상 n-1 단계 만족 => n 단계 만족함을 증명이라고 설명했으나 실제로는 n-1단계보다는 이전단계, n단계보다는 다음 단계라고 받아들이는게 맞다. 여기서도 이전단계를 n-1단계가 아니라 점화식의 구조를 이용하기 위해 n/2 단계로 설정했다. 따라서 이 증명의 목표는 T(n/2)<=c*(n/2)*log(n/2)가 성립함을 가정했을 때, T(n)<=c*n*logn이 성립함을 보이는 것이다.
우선 귀납적 가정을 이용해 식을 (1)과 같이 대입하여 정리할 수 있다.
이를 전개해서 살펴보면 (2)와 같은 꼴로 정리할 수 있게 된다. 이제 이 식이 c*n*logn보다 작거나 같음만 보이면 증명이 끝나게 된다.
(2) 식에서 c*n*logn 뒤에 붙은 식이 0 이하임을 증명하면 자연스럽게 c*n*logn보다 작거나 같음이 증명된다.
이 식을 (4)와 같이 정리할 수 있고, n은 양수이므로, 1-c*log2가 0 이하인 c(>=1/log2)를 잡으면 식을 만족하게 된다.
따라서 경계 조건 n=2 이상의 모든 수에 대해 T(n)<=c*n*logn임을 알 수 있다.
사실 이 정도면 비교적 증명이 간단히 된 편이라고 할 수 있다. 추정 후 증명 과정에서는 부등식을 적절히 변형하여 원하는 식의 형태로 만드는 기술을 많이 요한다. 간단하게 예를 들자면 어떤 값의 상한 값을 이용하여 대소 관계를 유지하면서 다른 식으로 바꾸는 등의 센스와 테크닉이 필요하다.
3. 마스터 정리 (Master Theorem)
마지막으로 마스터 정리는 점화식이 특정한 구조를 띠고 있을 때 공식처럼 바로 시간복잡도를 알아낼 수 있는 방법이다. 필자도 마스터 정리가 증명된 자세한 속사정은 모르기 때문에 어떻게 사용하는지만 정리해보았다.
우선 마스터 정리의 전제는 점화식이 T(n) = a*T(n/b) + f(n) 꼴을 띠고 있어야 한다는 점이다. 그리고, h(n)을 n^(
)로 정의한다. 이후 f(n)과 h(n)을 비교하여 점화식의 시간복잡도가 결정된다. 사실 아래 (1)~(3)을 봐도 잘 와닿지 않을 수 있다. 좀 더 직관적으로 설명을 우선 하고 수학적 식을 살펴보자.
(1) f(n)보다 h(n)이 다항식의 비율로 더 크면 T(n)의 시간복잡도가 Θ( h(n) )을 따른다.
(2) h(n)보다 f(n)이 다항식의 비율로 더 크면 T(n)의 시간복잡도가 Θ( f(n) )을 따른다. (추가 조건 제외한 내용)
(3) f(n)과 h(n)이 다항식의 비율로 차이가 없다면 T(n)의 시간복잡도가 Θ( h(n)*logn )을 따른다.
(1)에서 어떤 양의 상수 ε 에 대해 f(n)/h(n) = O(1/n^ε) 라는 것은 h(n)이 f(n)보다 약 n^ε 배 크다는 것이므로 다항식의 비율로 h(n)이 더 크다는 것을 의미한다. 이러한 원리로 (2)와 (3)에 있는 식도 이해할 수 있을 것이라 생각한다. 즉, 시간복잡도가 f(n)와 h(n) 중 더 큰 놈을 따라가되, f(n)과 h(n)이 동일하면 logn을 곱한 것을 따라간다는 것이 마스터 정리의 내용이라고 할 수 있을 것 같다. 다만 (2) 조건에 부가적인 조건이 붙는데, 마스터 정리의 증명과정에서 파생된 내용이고 (2) 조건을 사용하기 위해서 증명해야 하는 부분이다. 자세한 내용은 필자도 모른다.
각 조건에 해당하는 예제이다. merge sort의 경우는 (3)에 해당하여 Θ(n*logn)을 따른다.
아래는 시간복잡도 계산 시 2^k=n으로 가정해도 되는 이유를 증명한 것이다.
[알고리즘] 정렬 - 버블 정렬, O(N^2) (0) | 2024.03.17 |
---|---|
[알고리즘] 정렬 - 선택 정렬, O(N^2) (0) | 2024.03.17 |
[알고리즘] Merge Intervals (LeetCode 56) (0) | 2024.03.07 |
[알고리즘] 레드 블랙 트리 (Red-Black Tree) 의 특징 (0) | 2024.03.06 |
[알고리즘] 알고리즘 분석의 기초 (0) | 2024.02.29 |