通用形式:T(n) = aT(n/b) + f(n)
所以我必须将n ^ logb(a)与f(n)进行比较
如果n^logba> f(n)是情况1 和T(n)=Θ(n^logb(a))
如果n^logba <f(n)是情况2 和T(n)=Θ((n^logb(a))(logb(a)))
那是对的吗？还是我误会了什么？
那情况3呢？什么时候适用？
最佳答案
我想您误会了。
如果n ^ logba> f(n)是案例1并且T(n)=Θ(n ^ logb(a))
在这里，您不必担心f(n)的结果，得到的是T(n)=Θ(n ^ logb(a))。
f(n)是T(n)的一部分..如果获得结果T(n)，则该值将包含f(n)。
因此，无需考虑该部分。
如果您不清楚，请告诉我。
关于algorithm - 了解主定理，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13430256/