728x90 반응형 점근적 접근1 [Algorithm] 점화식 점근적 접근 방식(반복 대치, 추정 후 증명) 점화식을 푸는 방법 중에서 반복 대치와 추정 후 증명에 대해 공부해보려 한다. 반복 대치 추정 후 증명 반복 대치 점화식을 잘게 쪼개어서 푸는 방법이다. (1) T(n) = T(n-1) + n 이라는 점화식이 있다고 하자. ( T(1) = 1 ) n에 n-1을 넣으면 T(n-1) = T(n-2) + n-1이 된다. 그럼 1번 점화식의 우변에 존재하는 T(n-1)에 그대로 대입하면 (2) T(n) = T(n-2)+ n + (n-1)이 된다. 원래 1번 점화식의 n에 n-2를 넣으면 T(n-2) = T(n-3) + n-2가 된다. 이를 2번 점화식의 우변에 존재하는 T(n-2)에 그대로 대입하면 (3) T(n) = T(n-3) + n +(n-1) + (n-2)가 된다. T(1)을 알고 있고 T(1)이 나올때.. 2022. 12. 5. 이전 1 다음 728x90 반응형