반응형
Recurrence relation
점화식이란?
- 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것
(ex) 등차수열, 팩토리얼
점근적 분석 방법의 종류?
(1) 반복 대치 : 더 작은 문제에 대한 함수로 반복해서 대치함
(2) 추정 후 증명 : 식의 모양을 보고 점근적 복잡도를 추정한 다음, 그 것의 옳음을 수학적으로 귀납적 증명
(3) 마스터 정리 : 특정 형식에 맞는 점화식의 복잡도를 계산이나 증명없이 알수있는 정리
반응형
'Algorithms' 카테고리의 다른 글
| 알고리즘 개념 7. 병합정렬 Merge sort (0) | 2020.11.10 |
|---|---|
| 알고리즘 개념 6. 삽입정렬 (Insertion sort) (0) | 2020.11.09 |
| 알고리즘 개념 4. 선택정렬 Selection sort (0) | 2020.11.03 |
| 알고리즘 개념 2. 점근적 표기 (Asymptotic notation) (0) | 2020.10.28 |
| 알고리즘 개념 1. 재귀(자기호출)와 귀납법 (0) | 2020.10.27 |
댓글