Rekurrenzrelationen mit Master-Theorem: Polynomfunktion

Question

lassen T(n) eine zunehmende Funktion

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

wo a >= 1 und b >= 2

sein Master theorem zu verwenden, eine der Bedingungen, die erfüllt werden muss, ist, dass f(n) eine sein sollte, Polynomfunktion.

In diesem Beispiel ist es eindeutig nicht

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

Das Buch zählt f(n)=n^(1/2) als Polynomfunktion, aber was ich gelehrt habe ist, dass wenn f(n) = n^a eine Polynom-Funktion ist, dann a eine natürliche Zahl sein muss. Gibt es eine besondere Bedingung?

Answer 1

Man könnte dies ein allgemeines Polynom nennen, aber es ist das, was beabsichtigt ist. Viele Sätze, die für "natürliche Zahl" -Polynome arbeiten, funktionieren auch für diese verallgemeinerten Polynome. Denken Sie nur an Differenzierung oder Integration.