차마시는 개발자

점화식 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현 1. 반복 대치 더 작은 문제에 대한 함수로 반복해서 대치해가는 방법 점근적 복잡도 계산 용의 $$ n = c^k $$ $$ n , \le , c^k , < , cn , 인, c^k이 , 하나 존재한다. $$ $$ 만약,임의의,상수,r에,대해,T(n),=,O(n^r)이라면, $$ $$ T(cn) ,=,O((cn)^r),=,O(c^rn^r),=,O(n^r)이므로,T(cn),=,T(n)이,된다. $$ 입력의 크기가 두배가 되어도 다항식 범위 내에 있는 점근적 복잡도는 변하지 않는다. $$ T(n), \le , T(2^k), \le , T(2n) $$ 2. 추정 후 증명 결론을 추정하고 수학적 귀납법으로 이용하여 증명하는 방법 수학적 귀납..