되풀이 관계 : 다항식 함수

Question

는 T(n)이 만족해야하는 조건의 하나 f(n)이 여야한다는 것이다

T(n) = aT(n/b)+f(n) 

여기서 a >= 1 및 b >= 2

가 Master theorem을 사용하는 증가 함수하자 다항식 함수. 이 예에서

는 명확하지

T(n) = 2T(n/4) + n^(1/2) + 42입니다.

이 책은 다항식 함수로 f(n)=n^(1/2)을 계산하지만, 내가 설명한 바에는 f(n) = n^a이 다항식 함수이면 a은 자연수 여야합니다. 특수한 상태가 있습니까?

Answer 1

일반화 된 다항식이라고 할 수 있지만 의도 한 것입니다. '자연수'다항식에 대해 작동하는 많은 정리가이 일반화 된 다항식에서도 작동합니다. 차별화 또는 통합을 생각하십시오.