[Discrete Mathematics] 점근적 분석법 - 추정 후 증명

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)\)