data-structures - 主定理-第二个案例问题

Question

给定以下递归方程:

T(n) = 5T(n/5)+(5sin^5(5n^5)+5)*n
T(n) = T(n/4)+2sin^2(n^4)

我可以很容易地看出这两个方程都符合主定理的第二种情况，

但由于sin是一个循环函数，似乎N足够大可能会使它真正接近于零。因此，对于两个常数 c1、c2(根据 theta 定义)，我们总能找到 N > N0这将不赞成它..

真的可以用主定理解决吗？

谢谢

Answer 1

我认为你是对的，Master Theorem 在这里不适用。这样做的原因是 f(n) 和 n^(log_b(a)) 之间的差异必须是多项式的。 (参见 Master Theorem Recurrences: What is exactly polynomial difference?)

在你的情况下:((5sin^5(5n^5)+5)*n)/(n^(log_5(5)))=(5sin^5(5n^5)+5和(2sin^2(n^4))/(n^(log_4(1)))= 2sin^2(n^4)，不是多项式，所以Master Theorem在这里无效案例。