![[Algorithm] 치환법(Substitutions Method)](https://blogimgs.pstatic.net/nblog/mylog/post/og_default_image_160610.png)
치환법이란? 치환법은 주어진 재귀식의 한계점을 예상하고 그것이 유효하다는 것을 수학적 귀납법을 이용해서 증명하는 방법입니다.
치환법은 다음과 같은 구조로 진행됩니다. 치환법 예제 예제 1번 T(n)=T(n/2)+d 예제 2번 T(n)=T(n-1)+1 예제 3번 T(n)=2T(n/2)+n 예제 4번 T(n)=2T(n1/2)+logn 마무리 치환법을 이용하면 분석하려는 재귀식의 성능이 예상과 동일한지를 확인할 수 있습니다.
하지만, 그 예상치보다 더 성능이 좋을 수도 나쁠 수도 있기에 어려가지를 고려해야 합니다. 핵심은 이미 널리 알려진 재귀식 분석 결과를 이용해서 구하려는 재귀식을 변형해야 하는 것입니다....
[Algorithm] 치환법(Substitutions Method)에 대한 요약내용입니다.
자세한 내용은 아래에 원문링크를 확인해주시기 바랍니다.
