与主定理的递归关系：多项式函数
Recurrence relations with master theorem: polynomial function
设T(n)为增函数
T(n) = aT(n/b)+f(n)
其中 a >= 1 和 b >= 2
要使用Master theorem，必须满足的条件之一是f(n)必须是多项式函数。
在这个例子中，显然不是
T(n) = 2T(n/4) + n^(1/2) + 42 .
书上把f(n)=n^(1/2)算作一个多项式函数，但我所学的是，如果f(n) = n^a是一个多项式函数，那么a一定是一个自然数。有什么特殊条件吗？
您可以将其称为广义多项式，但它就是我们想要的。许多适用于 'natural number' 多项式的定理也适用于这些广义多项式。想想微分还是整合。
设T(n)为增函数
T(n) = aT(n/b)+f(n)
其中 a >= 1 和 b >= 2
要使用Master theorem，必须满足的条件之一是f(n)必须是多项式函数。
在这个例子中，显然不是
T(n) = 2T(n/4) + n^(1/2) + 42 .
书上把f(n)=n^(1/2)算作一个多项式函数，但我所学的是，如果f(n) = n^a是一个多项式函数，那么a一定是一个自然数。有什么特殊条件吗？
您可以将其称为广义多项式，但它就是我们想要的。许多适用于 'natural number' 多项式的定理也适用于这些广义多项式。想想微分还是整合。