최선의 경우, 최악의 경우, 평균의 경우를 분석할 때 상한, 하한, 평균 수행 시간을 구하려 한다. 그 중에서 집중해야하는 부분은 상한이다. 왜냐하면 알고리즘의 하한을 아는 것은 실용적으로 중요하지 않기 때문이다.
- 점근적 분석 가이드라인 //중요!!!
(알고리즘의 수행 시간을 계산하는 데 도움이 되는 몇 가지 일반적인 규칙이 있다.)
1) 루프: 루프의 수행 시간은 루프 안의 구문들의 수행 시간(조건문 수행 시간 포함해서) 곱 하기 반복 횟수가 최대 값이 된다.
//n번 수행
for( i=1; i<=n; i++)
m = m + 2; //일정한 시간, c
전체 시간 = 상수 c*n = O(n).
2) 중복 루프: 안쪽에서 바깥쪽 순서로 분석한다. 전체 수행 시간은 각각의 루프의 수행 시간을 곱해서 구한다.
// 바깥 루프는 n번 수행
for(i=1; i<=n; i++) {
// 안쪽 루프 n번 수행
for(j=1; j<=n; j++)
k=k+1;
}
전체 시간 = c*n*n = O(n^2)
3) 연속된 구문들: 각 구문의 복잡도를 더한다.
x = x + 1; //일정한 시간
//n번 수행
for(i=1; i<=n; i++)
m = m + 2; //일정한 시간
//바깥 루프 n번 수행
for(i=1; i<=n; i++) {
//안쪽 루프 n번 수행
for(j=1; j<=n; j++)
k = k+1; //일정한 시간
}
전체 시간 = c0 + c1*n + c2*n^2 = O(n^2)
4) If-then-else 구문: 최악의 경우 수행 시간은 조건문 수행 시간에 then 부분 또는 else 부분 중에 더 오래 걸리는 쪽 시간을 더한 경우이다.
//조건문: 상수
if(length()==0) {
return false; //then 부분 : 상수
}
else { //else 부분: (상수 + 상수) * n
for(int n=0; n < length(); n++) {
// 또 다른 if: 상수 + 상수 (else 부분 없음)
if(!list[n].equals(otherList.list[n]))
// 상수
return false;
}
}
전체 시간 = c0 + c1 + (c2 + c3)*n = O(n)
5) 로그형 복잡도: 어떤 알고리즘의 문제의 크기를 일부(보통은 1/2)를 줄이는 데 일정한 시간이 걸린다면 O(logn)이다.
for( i=1; i<=n; )
i = i*2;
// i의 값이 매번 두 배가 된다.
k번째 단계엔 2^k = n이 되고 루프를 빠져나온다.
log(2^k) = logn
k*log2 = logn
k = logn // 2를 베이스로 한다고 가정하면
전체 시간 = O(logn)
또 다른 예
for(i=n; i<=2; )
i = i/2;
이진 검색(n페이지의 사전에서 단어 찾기)
사전의 중앙을 찾는다.
단어가 중앙의 왼쪽인가? 오른쪽인가?
왼쪽이나 오른쪽 부분을 가지고 단어를 찾을 때까지 앞의 과정을 반복한다.
- 각 표기법의 특성
이행성: f(n) = Θ(g(n))이고, g(n) = Θ(h(n))이면 => f(n) = Θ(h(n))이다.
(O와 Ω에 대해서도 성립)
반사성: f(n) = Θ(f(n))이다. (O와 Ω에 대해서도 성립)
대칭성: g(n) = Θ(f(n))일 경우에만 (iff, if and only if) f(n) = Θ(g(n))이다.
전치 대칭성: g(n) = Ω(f(n))일 경우에만 (iff, if and only if) f(n) = O(g(n))이다.
- 자주 사용되는 로그 함수와 급수
조화급수
∑(1/k) = 1 + 1/2 + ... + 1/n ≈ log n
∑(log k) ≈ n*log n
∑(k^p) = 1^p + 2^p + ... + n^p ≈ (1/p+1)*(n^(p+1))
재귀 관계식이 T(n) = aT(n/b)
마스터 정리 2. a = b^k일 경우
a. p > -1이면 T(n) = Θ(((n^(logba))*((log n)^(p+1)))
b. p = -1이면 T(n) = Θ(((n^(logba))*(log(log n)))
c. p < -1이면 T(n) = Θ((n^(logba))
마스터 정리 3. a < b^k일 경우
a. p >= 0이면 T(n) = Θ((n^k)*((log n)^p))
b. p < 0이면 T(n) = Θ(n^k)
// a, b, k, p 값을 잘 구하는 것이 중요
- 차감 정복 점화식을 위한 마스터 정리
어떤 상수 c, a > 0, b > 0, k >= 0과 함수 f(n)에서 다음과 같은 속성을 갖는다고 하자.
T(n) = c if n =< 1
= a*(T(n-b) + f(n)), if n > 1
f(n)이 O(n^k) 안에 있다면
O(n^k), if a < 1
T(n) = O(n^(k+1)), if a = 1
O((n^k)*(a^(n/b))), if a > 1
- 상각 분석
상각 분석은 작업 시퀀스의 시간평균화된 수행 시간을 계산하는 것을 말한다.
//작업 시퀀스에 대한 최악의 경우 분석
상각 분석은 대부분의 작업은 단순하지만 몇몇 작업이 시간이 많이 걸리는 작업으로 구성된 작업 시퀀스의 분석에 주로 이용된다.
시간이 많이 걸리는 작업의 빈도가 특별히 낮다는 것을 증명할 수만 있다면, 단순한 작업의 수행 시간으로 이런 작업의 시간을 커버하고 단순한 작업의 한계만 계산할 수 있다.
일반적인 접근 방법은 작업 시퀀스의 각 작업에 가공의 비용을 할당하는데, 이 가공의 비용의 총합이 시퀀스의 실제 비용의 총합을 넘지 않도록 하는 것이다. 이 가공의 비용이 작업의 상각 비용이라고 불린다.
댓글 없음:
댓글 쓰기