Asymptotic Analysis Method
(점근적 분석법)
- 점화식* 의 점근적 복잡도를 구하는 방법
- 대표적으로 세 가지 방법이 존재 (반복 대치, 추정 후 증명, 마스터 정리)
* 점화식 (Recurrence) : 어떤 함수를 자신과 똑같은 함수를 이용해 표현한 식
ex) 피보나치 수열 : \(F(n) = F(n-1) + F(n-2)\)
ex) 팩토리얼의 함수적 표현 : \(f(n) = n * f(n-1)\)
추정 후 증명
Substitution Method
- 점화식의 모양을 보고 점근적 복잡도를 추정한 후, 귀납적으로 증명하여
점근적 시간복잡도(Time Complexity)를 구하는 방법
ex) 점화식 \(T(n) ≤ 2T({n \over 2}) + n\) 의 추정 후 증명법을 통한 풀이
[추정]
충분히 큰 \(n\)에 대하여 \(T(n) \leq cn\log{n}\)인 양의 상수 \(c\)가 존재한다.
즉, \(T(n) = O(n\log{n})\) 이다.
[증명]
i. 귀납법 상 경계조건
\(T(2) \leq 2c\log{2}\) 를 만족하는 \(c\) 가 존재함 (\(\because T(1) \leq c\log{1}\) 은 불가능하므로)
* 경계조건으로 \(T(2)\) 가 아닌, 훨씬 큰 상수 \(a\)에 대해 \(T(a) \leq ca\log{a}\) 를 보여도 무관함
* 경계조건을 만족시키는 경계치는 항상 잡을 수 있으므로 경계조건을 확인하는 과정은 생략해도 무관함
ii. 귀납적 가정 및 전개
\(T({n \over 2}) \leq c({n \over 2})\log{{n \over 2}}\) 를 만족한다 가정하면,
\(T(n) \leq 2T({n \over 2}) + n\)
\(\leq 2c({n \over 2})\log{n \over 2} + n\)
\(= cn\log{n} - cnlog{2} + n\)
\(= cn\log{n} + (-c\log{2} + 1)n \quad\quad (\therefore c \geq {1 \over \log{2}})\)
\(\leq cn\log{n}\)
\(∴ T(n) = O(n\log{n})\)
추정 후 증명 과정에서 귀납적 증명 시, 경계조건확인 과정은 생략 가능하다.
- 일반적으로 \(T(n) = f(n)\) 임을 보이기 위해 상수 \(a\)를 경계치로 잡으면 \(T(a)\)도 상수가 되므로
\(f(n)\)이 양수인 한 \(T(a) ≤ cf(a)\) 를 만족시키는 \(c\)가 항상 존재한다. 그러므로 점근적 복잡도의
귀납적 증명 시에 굳이 경계조건을 확인하지 않아도 된다.
- 단, 귀납적 가정에서 사용한 상수 \(c\)와 결론에서 사용하는 상수 \(c\)는 반드시 같아야 함.
수학적 귀납법의 전개방법
Way 1. \(n = k\) 일 때 성립하면 \(n = k + 1\) 일 때도 성립함
Way 2. \(n₁ ≤ k < n\) 인 모든 \(k\)에 대해 성립하면 \(n\)일 때도 성립
Way 3. \(n = k\) 일 때 성립하면 \(n = 2k\) 일 때도 성립
ex) 점화식 \(T(n) ≤ 2T({n \over 2} + 10) + n\) 의 추정 후 증명법을 통한 풀이
[추정]
충분히 큰 \(n\) 에 대하여 \(T(n) ≤ cn\log{n}\) 인 양의 상수 \(c\)가 존재한다.
즉, \(T(n) = O(n\log{n})\) 이다.
[증명]
\(T(n) ≤ 2T({n \over 2} + 10) + n\)
\(≤ 2c({n \over 2} + 10)\log({n \over 2} + 10) + n\)
※ 수학적 귀납법 전개방법 중 Way 2 방법으로 진행하면, \({n \over 2} + 10 < n\) 의 조건이 생성됨, 초기 조건 \(n_1\) 은 무시, 즉 \(20 < n\)
\(= cn\log({n \over 2} + 10) + 20c\log({n \over 2} + 10) + n\)
\(\leq cn\log{3n \over 4} + 20c\log{3n \over 4} + n\)
※ 식의 전개를 용이하게 하기 위해 식을 간소화 하는 과정, 이 과정에서 조건 \({n \over 2} + 10 \leq {3n \over 4}\) 가 생성됨, 즉 \(40 \leq n\)
\(= cn\log{n} + cn(\log{3} - \log{4}) + 20c\log{3n \over 4} + n\)
\(= cn\log{n} + (c(\log{3} - \log{4}) + 1)n + 20c\log{3n \over 4}\)
\(≤ cnlogn\)
※ \(c(\log{3} - \log{4} + 1)n + 20c\log{3n \over 4}\) 의 값이 음수가 되도록 \(c\)의 값을 충분히 크게 설정해야 함
\(∴ T(n) = O(nlogn)\)
ex) 점화식 \(T(n) ≤ 2T(n/2) + 1\) 의 추정 후 증명법을 통한 풀이
(귀납적 과정에서 상수 \(c\)에 관한 설정값이 증명의 성패를 좌우함을 중점으로)
[추정]
i. (실패한 가정) 충분히 큰 \(n\) 에 대해 \(T(n) ≤ cn\) 인 양의 상수 \(c\) 가 존재한다. 즉, \(T(n) = O(n)\)이다.
ii. (실패한 가정) 충분히 큰 \(n\) 에 대해 \(T(n) ≤ cn + 2\) 인 양의 상수 \(c\) 가 존재한다. 즉, \(T(n) = O(n)\)이다.
iii. (성공한 가정) 충분히 큰 \(n\)에 대해\(T(n) ≤ cn - 2\)인 양의 상수\(c\)가 존재한다. 즉, \(T(n) = O(n)\)이다.
[증명]
i. T(n) ≤ cn
\(T(n) = 2T({n \over 2}) + 1\)
\(\leq 2{cn \over 2} + 1\)
\(= cn + 1\)
(\(cn + 1 ≤ cn\) 임을 증명할 수 없으므로 더 이상 진행 불가)
ii. T(n) ≤ cn + 2
\(T(n) = 2T({n \over 2}) + 1\)
\(\leq 2({cn \over 2} + 2) + 1\)
\(= cn + 5\)
(i. 의 경우와 마찬가지로 증명 실패)
iii. T(n) ≤ cn - 2
\(T(n) = 2T({n \over 2}) + 1\)
\(\leq 2({cn \over 2} - 2) + 1\)
\(= cn - 3\)
\(\leq cn - 2\)
\(\therefore T(n) \leq cn - 2 \iff T(n) = O(cn-2) = O(n)\)
