[알고리즘] 1주차: 03. 점화식과 점근적 복잡도 분석

03. 점화식과 점근적 복잡도 분석

1. 점화식 : 어떤 함수를 자신과 똑같은 함수를 이용해 나타내는 것

    예) 등차수열, 피보나치 수열, n!재귀함수의 복잡도를 구하는데 유용 (알고리즘의 수행시간을 점화식으로 표현 가능) 

2. 점화식으로 표현된 식의 점근적 복잡도를 구하는 방법 : 반복 대치, 추정 후 증명, 마스터 정리

3. 반복 대치 : 더 작은 문제에 대한 함수로 반복해서 대치해서 계산하는 방법직관적이긴 한대 길어지면 복잡해짐

 

4. 추정 후 증명 : 결론을 먼저 추정하고 수학적 귀납법으로 옳은지 증명하는 방법

• 유의 사항
  1. 직관적이지 않을 때가 있음 (경험 필요)
  2. 추정을 의미있게 해야함
  3. 점화식의 모양에 익숙해져야한다 -> 마스터 정리 이용

5. 마스터 정리 : 형식에 맞는 점화식의 복잡도를 바로 알 수 있는 방법

---

문제

1. 점화식의 점근적 분석 방법은 반복대치, 추정 후 증명, 마스터 정리의 세가지가 있다. 수학적 귀납법을 활용하여 복잡도를 분석하는 방식을 ( 추정 후 증명 ) 이라하고, 특정한 모양을 가진 재귀식에서 바로 복잡도를 계산해 내는 방법을 ( 마스터 정리 ) 이라 한다. 점화식을 더 작은 변수에 대한 점화식으로 대치하는 작업을 반복하면서 경계조건에 이를때까지 수식을 전개하는 것을 ( 반복대치 ) 방법이라 한다.
2. 어떤 함수를 자신과 똑같은 함수를 이용해 나타내는 것을 ( 점화 )식이라 한다.

출처

K-MOOC : 선복근 교수님 - 알고리즘

http://www.kmooc.kr/courses/course-v1:HOSEO+HOSEOSW01+2021_12/about 

알고리즘