입력의 개수 n이 2^k라고 가정하고 점근적 복잡도를 계산해도 되는가? 입력의 개수 n이 3^k라고 가정하고 점근적 복잡도를 계산해도 되는가? 일반적인 n에 관한 점근적 복잡도와 2^k인 n에 관한 점근적 복잡도는 같은가? 일반적인 n에 관한 점근적 복잡도와 3^k인 n에 관한 점근적 복잡도는 같은가?
1. 아무 n이든지 n에 관한 점근적 복잡도와 2n에 관한 점근적 복잡도는 같다. (점근적 복잡도가 다항식이라는 가정 필요) 예를 들어 n에 관한 점근적 복잡도가 O(n^3)이면 2n에 관한 점근적 복잡도는 O(8 n^3)이다. 예를 들어 n에 관한 점근적 복잡도가 O(n^r)이면 2n에 관한 점근적 복잡도는 O(2^r * n^r)이다. 2. 아무 n이든지 n<=2^{k}<2n 인 k를 찾을 수 있다. 3. 아무 n이든지 n에 관한 점근적 복잡도와 2^k에 관한 점근적 복잡도와 2n에 관한 점근적 복잡도는 같다
추정후 증명
결론을 추정하고 수학적 귀납법으로 이용하여 증명하는 방법이다.
T(n) = 2T(n/2) + n
<추정> T(n) = O(nlogn), 즉T(n) ≤cnlogn
<증명>
T(n) = 2T(n/2) + n
≤2c(n/2)log(n/2) + n
= cnlogn − cnlog2 + n
= cnlogn + (−clog2 + 1)n
≤ cnlogn (만족하는 c 존재)
T(n) = 2T(n/2) + 1
<추정> T(n) = O(n), 즉 T(n) ≤cn
<증명>
T(n) = 2T(n/2) + 1
≤2c(n/2) + 1
= cn + 1 (추정에 맞지 않음)
<추정> T(n) ≤cn- 2
<증명>
T(n) = 2T(n/2) + 1
≤2(c(n/2) - 2) + 1
= cn – 3
≤ cn – 2 (만족하는 c 존재)
마스터 정리
형식에 맞는 점화식의 복잡도를 바로 알 수 있다.
T(n) = aT(n/b) + f(n)와 같은 모양을 가진 점화식은 마스터 정리에 의해 바로 결과를 알 수 있다
n^(log_ba) = h(n)이라 할 때
① 어떤 양의 상수 ε에 대하여 f(n)/h(n) = O(1/n^ε)이면, T(n) = Θ(h(n))이다.
② 어떤 양의 상수 ε에 대하여 f(n)/h(n) = Ω(n^ε)이고, 어떤 상수 c(< 1)와 충분히 큰 모든 n에 대해 af(n/b) ≤ cf(n)이면 T(n) = Θ(f(n))이다.
③ f(n)/h(n) = Θ(1)이면 T(n) = Θ(h(n)logn)이다.
직관적 의미
① h(n)이 더 무거우면 h(n)이 수행 시간을 결정한다.
② f(n)이 더 무거우면 f(n)이 수행 시간을 결정한다.
③ h(n)과 f(n)이 같은 무게이면 h(n)에 logn을 곱한 것이 수행 시간이 된다.
기본개념
다음 두 문제가 해결되는 과정을 그림과 같이 설명한다. (리프 노드의 문제 크기가 1이 될때까지 해결한다)
T(n) = 3T(n/2) + f(n)
T(n) = 2T(n/4) + f(n)
정리하면 T(n) = aT(n/b) + f(n) 이라는 점화식은 한 레벨을 내려올때마다 1/b로 줄어든, 자식이 a개인 T(n/b)로 이루어진다. 총 비용에서 Θ(n^logb(a)는 리프 노드 Θ(1)을 모두 더한 결과이며 Σ(j=0 -> logb(n-1)의 a^j*f(n/b^j)는 f(n)부터 리프 노드의 바로 위의 문제까지 더한 결과이다. 따라서 이 두 비용 중 더 큰 값이 시간복잡도로 결정되며 두 비용이 비슷하다면 logb(n)을 곱한 값이 시간복잡도가 된다.
sample(A[], p, r) {
if (p = r) return 1;
sum <- 0;
for i <- 1 to n
sum <- sum + A[i];
q <- ⌊(p+r)/2⌋;
tmp <- sum + sample(A, p, q) + sample(A, q+1, r);
return tmp;
}
sample(A[], p, r) {
if (p >= r) return 1;
sum <- 0;
for i <- p to r
sum <- sum + A[i];
q <- ⌊(r-p+1)/3⌋;
tmp <- sum + sample(A, p, p+q-1) + sample(A, p+2q, r);
return tmp;
}