Asymptotic Analysis Method
(점근적 분석법)
- 점화식* 의 점근적 복잡도를 구하는 방법
- 대표적으로 세 가지 방법이 존재 (반복 대치, 추정 후 증명, 마스터 정리)
* 점화식 (Recurrence) : 어떤 함수를 자신과 똑같은 함수를 이용해 표현한 식
ex) 피보나치 수열 : \(F(n) = F(n-1) + F(n-2)\)
ex) 팩토리얼의 함수적 표현 : \(F(n) = n * F(n-1)\)
반복 대치
- 점화식을 반복하여 대치해가면서 점화식을 전체적으로 나열시킨 후에
점근적 시간복잡도(Time Complexity)를 구하는 방법
ex) 팩토리얼값(n!)을 구하는 알고리즘의 시간복잡도 분석과정
Factorial(n){
if (n = 1) return 1; // 1
else return (n * Factorial(n-1)); // 2
}Factorial Algorithm
결과값을 구하는 데 소요되는 시간을 \(T(n)\) 이라 하면
\(T(n) = T(n-1) + c\) (\(c\) : 자기호출을 제외한 나머지의 수행 시간)
으로 표현이 가능하다.
\(n\)의 계승을 구하는 시간은 \(n-1\)의 계승을 구하는 시간에 상수시간을 더한 형태이다.
여기서, 상수 시간 c 는 위 소스코드의 1번 문장과 2번 문장의 곱셈 연산을 수행하는데 걸리는 시간이다.
이제 반복 대치를 통해 \(T(n)\) 을 전개시켜보자.
\(T(n) = T(n-1) + c\)
\(= T(n-2) + c + c = T(n-2) + 2c\)
\(= T(n-3) + c + 2c = T(n-3) + 3c\)
···
\(= T(1) + (n-1)c\)
\(≤ c + (n-1)c = cn\) (\(\therefore T(1)\) : \(1!\)을 계산하는데 소요되는 시간이고, 이는 상수시간 \(c\)보다 작은 수치일수 밖에 없음)
\(\therefore T(n) ≤ cn\) 이므로 \(T(n) = O(n)\) 으로 표현가능하다.
ex) 병합정렬(Merge Sort) 알고리즘의 시간복잡도 분석과정
MergeSort(A[], p, r){
if (p < r) Then {
q ← ┖(p + r) / 2┚;
MergeSort(A, p, q);
MergeSort(A, q + 1, r);
Merge(A, p, q, r);
}
}
Merge(A[], p, q, r){
// 정렬되어 있는 두 배열 A[p ~ q] 와 A[q+1 ~ r] 를
// 원소 간 순서를 고려하며 합쳐서
// 정렬된 하나의 배열 A[p ~ r]을 만듦
}Merge Sort Algorithm (Pseudo Code)
* Summary of Merge Sort
- 정렬할 배열을 이등분한 다음, 분리된 두 배열을 정렬 우선순위에 맞춰서 하나의 배열로 병합시킴
- 단, 이등분 된 배열의 원소수가 2개 이상일 경우, 이등분된 배열을 대상으로 병합정렬을 재귀적으로 실행시킴
병합 정렬에서 대소 비교에 소요되는 시간(횟수)을 \(T(n)\) 이라 하면
(대소 비교 횟수가 전체 수행 시간의 기준이 되므로)
\(T(n) \leq 2T({2 \over n}) + n\)
으로 표현이 가능하다.
\(T({2 \over n})\)는 이등분된 배열을 병합 정렬하는 데 필요한 총 비교횟수이며,
여기서 \(n\)은
" Merge(A, p, q, r); " 문 에서 필요한 최대 비교 횟수 \(n-1\) 과
" if (p < r) then " 문 에서 실행되는 1회의 비교 횟수를 더한 값이다.
이제, 위의 수식 \(T(n) \leq 2T({2 \over n}) + n\) * 을 반복 대치를 통해 전개해 보면
\(T(n) \leq 2T({n \over 2}) + n\)
\(≤2(2T({n \over 4})+{n \over 2}) + n = 2²T({n \over 2²}) + 2n\)
\(≤2²(2T({n \over 2³})+{n \over 2²})+2n = 2³T({n \over 2³}) + 3n\)
···
\(\leq 2^{k}T({n \over 2^k}) + kn = nT(1) + kn = n + n\log{n} (\because n = 2^k \iff k = \log{n}, T(1) = 1)\)
\(= O(nlogn)\)
* 여기서 \(n\)을 오버헤드라 표현함 (Overhead : 간접적, 추가적으로 요구되는 값)
* 일반적으로, \(n=2^k\)로 가정함 (\(k ∈ N\), 다항식으로 표현되는 복잡도에 성립되는 논리)
pf) \(n \geq 2^k < 2n\)인 \(2^k\)이 하나 존재함
즉, 어떠한 \(n\)이라도 \(n\) 과 \(2n\) 사이에 \(2\)의 멱수가 하나 존재함
임의의 상수 \(r\)에 대해 \(T(n) = O(n^r)\) 이라면 \(T(2n) ⇔ O((2n)^r) ⇔ O((2^r)*(n^r)) ⇔ O(n^r)\) 이므로 \(T(2n) = T(n)\)임
즉, 입력의 크기(\(n\))가 두 배(\(2n\))가 되어도 다항식 범위 내에 있는 점근적 복잡도는 변하지 않음
알고리즘 복잡도 함수는 단조 증가 함수라 가정하므로 (입력이 많을 경우 보다 입력이 적은 경우 실행시간이 더 짧다고 가정)
\(T(n) ≤ T(2^k) ≤ T(2n)\) 이다.
여기서, \(T(n) = T(2n)\) 이므로
\(T(n) = T(2^k) = T(2n)\) 이다
즉, \(n\)의 오른쪽에서 처음 만나는 \(2\)의 멱수에 대한 함수도 항상 \(n\)에 대한 함수와 같은 점근적 복잡도를 가지므로
\(n = 2^k\)로 가정한다 해도 점근적 분석의 결과는 같다는 결론이 나옴
점근적 분석에서의 관행적 표현
\(T(n) ≤ 2T(n/2) + n\) \(\iff\) \(T(n) ≤ 2T(n/2) + O(n)\)
- 집합으로서의 \(O(n)\)이 아닌, \(O(n)\)에 속하는 한 함수를 대신하여 표현하는 방법
- 식을 자세히 기술할 필요가 없는 경우에 이용
