Asymptotic Analysis Method
(점근적 분석법)
- 점화식* 의 점근적 복잡도를 구하는 방법
- 대표적으로 세 가지 방법이 존재 (반복 대치, 추정 후 증명, 마스터 정리)
* 점화식 (Recurrence) : 어떤 함수를 자신과 똑같은 함수를 이용해 표현한 식
ex) 피보나치 수열 : \(F(n) = F(n-1) + F(n-2)\)
ex) 팩토리얼의 함수적 표현 : \(f(n) = n * f(n-1)\)
마스터 정리
Master Theorem
- 특정 형태의 재귀식에서 바로 결과를 도출하는 방법
- 입력의 크기가 \(n\)인 문제를 풀기 위해 입력의 크기가 \({b \over n}\) 인 문제를 풀고,
나머지 \(f(n)\) 의 오버헤드가 필요한 알고리즘의 점화식을 풀 수 있음
\(T(n) = aT({n\over b}) + f(n)\) : 마스터정리가 적용 가능한 식의 형태
\(f(n)\)
크기가 n인 문제의 최상위 레벨에서 발생하는 호출 이외의 오버헤드로,
크기가 다른 문제들 간의 관계를 반영하는 비용
Recursion 상에서 가장 상위 레벨에서의 오버헤드만 반영하고 하위 레벨에서의 오버헤드는 반영하지 않음
\(h(n) = n^{\log_{b} a}\)
반복적인 자기호출 끝에 마지막으로 크기가 1인 문제를 만나는 횟수
\(h(n)\) 과 \(f(n)\) 의 상대적 무게에 따라 전체 복잡도가 결정됨
마스터정리 (Original)
\( a \geq 1, b > 1 \) 에 대해 \(T(n) = aT({n \over b}) + f(n) \) 인 점화식에서, \(n^{\log_{b} a} = h(n)\) 일 때
1. 어떤 양의 상수 \(\epsilon\) 에 대해 \({f(n) \over h(n)} = \Omega({1 \over n^{\epsilon}})\) 이면,
\(T(n) = \Theta(h(n))\) 이다.
2. 어떤 양의 상수 \(\epsilon\) 에 대해 \({f(n) \over h(n)} = \Omega(n^{\epsilon})\) 이고,
어떤 상수 c < 1 와 충분히 큰 모든 n 에 대해 \(af({n \over b}) \leq cf(n)\) * 이면
\(T(n) = \Theta(f(n))\) 이다.
* Recursion 상에서 하위 레벨에서의 오버헤드 값이 상위 레벨에서의 오버헤드 값보다 같거나 작아야 함을 의미
3. \({f(n) \over h(n)} = \Theta(1)\) 이면
\(T(n) = \Theta(h(n)\log{n})\) 이다.
마스터 정리 (Approximate)
1. \(\lim_{n \to \infty} {f(n) \over h(n)} = 0\) 이면
\(T(n) = \Theta(h(n))\) 이다.
2. \(\lim_{n \to \infty} {f(n) \over h(n)} = \infty\) 이고,
충분히 큰 모든 n에 대해 \(af({n \over b} \leq f(n)\) 이면
\(T(n) = \Theta(f(n))\) 이다.
3. \({f(n) \over h(n)} = \Theta(1)\) 이면
\(T(n) = \Theta(h(n)\log{n})\) 이다.
마스터 정리 (More approximate)
1. h(n) 이 더 무거우면 h(n) 이 수행 시간을 결정한다.
2. f(n) 이 더 무거우면 f(n) 이 수행 시간을 결정한다.
3. h(n) 과 f(n) 이 같은 무게이면 h(n) 에 \(\log{n}\) 을 곱한 것이 수행 시간이 된다.
* 마스터 정리 원형과의 차이
- \(\lim_{n \to \infty} {f(n) \over h(n)} = 0\) \(\iff\) h(n) 이 f(n) 을 압도함
- \({f(n) \over h(n)} = O({1 \over n^{\epsilon}})\) \(\iff\) h(n) 이 f(n) 을 적어도 다항식의 비율로 압도함
= 원형과 근사형의 의미가 정확히 일대일로 일치하진 않음
ex) 점화식 \(T(n) = 2T({n \over 3}) + c\) (c : Constant) 의 마스터정리를 통한 풀이
\(T(n) = aT({n\over b}) + f(n)\) 에서
\(a = 2, b = 3, h(n) = n^{\log_{3} 2}, f(n) = c\) 이다.
\(\lim_{n \to \infty} {f(n) \over h(n)} = \lim_{n \to \infty} {c \over n^{\log_{3} 2}} = 0\) 이므로 마스터 정리 중 1번 유형에 속함
\(\therefore T(n) = \Theta(n^{log_{3} 2})\)
ex) 점화식 \(T(n) = 2T(\sqrt{n}) + \log_{2} n\) 의 마스터정리를 통한 풀이
(마스터 정리 형태와 상이한 경우 → 변수 치환법 이용)
\(T(n) = 2T(\sqrt{n}) + \log_{2} n\) 에서
\(n = 2^m\) 이라 하자.
\(T(n) = 2T(\sqrt{n}) + \log_{2} n\) \(\iff\) \(T(2^m) = 2T(2^{m \over 2}) + m\)
여기서 새로운 형태의 점화식
\(S(m) = 2S({m \over 2}) + m\) 으로 표현 가능하다.
여기서 마스터 정리를 이용하면
\(a = 2, b = 2, h(m) = m^{\log_{2} 2} = m, f(m) = m\) 이고,
\({f(m) \over h(m)} = \Theta(1)\) 이다.
\(\therefore S(m) = \Theta(m\log{m})\)
\(\therefore T(n) = T(2^m) = S(m) = \Theta(m\log{m}) = \Theta(\log{n}\log{\log{n}})\)
