漸化式：多項式関数

Question

を満たさなければならない条件の一つはf(n)があるべきであるということである、T(n)は増加関数

a >= 1と b >= 2

がMaster theoremを使用するには

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

なりましょう多項式関数。この例では

は、それが明確に

T(n) = 2T(n/4) + n^(1/2) + 42ではありません。

本は多項式関数としてf(n)=n^(1/2)を数えますが、f(n) = n^aが多項式関数ならば、aは自然数でなければなりません。特別な条件はありますか？

Answer 1

一般化された多項式と呼ぶこともできますが、それは意図されたものです。 「自然数」多項式のために働く多くの定理も、これらの一般化された多項式のために働く。差別化や統合を考えてみてください。