점화식
-어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것
-자기호출을 사용하는 함수의 복잡도를 구하는데 유용하게 쓰임
점화식의 점근적 분석 방법
-반복대치
-추정 후 증명
-마스터 정리
1) 반복 대치
(예1) n!
factorial(n)
{
if(n=1) return 1;
return n*factorial(n-1);
}
(예1 해답) T(n)=T(n-1)+c
T(1)≤c
T(n)=T(n-1)+c=T(n-2)+2c=...=T(1)+(n-1)c=cn
∴T(n)=O(n)
2) 추정 후 증명
(문제) T (n) = 2T (n/2) + n 추정: T(n) = O(nlogn), 즉 T(n) ≤ cn log n를 만족하는 c가 존재한다
<증명> 경계조건: T(2) ≤ c2log2를 만족하는 c가 존재한다.
귀납적 가정과 전개
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 더이상 진행 불가
3) 마스터 정리
'알고리즘' 카테고리의 다른 글
| 쉽게 배우는 알고리즘-08집합의 처리 (0) | 2023.10.23 |
|---|---|
| 쉽게 배우는 알고리즘-06검색트 (1) | 2023.10.23 |
| 쉽게 배우는 알고리즘-05선택 알고리즘 (0) | 2023.10.23 |
| 쉽게 배우는 알고리즘-04정렬 (1) | 2023.10.23 |
| 쉽게 배우는 알고리즘-02 알고리즘 설계와 분석의 기초 (1) | 2023.10.23 |