给定以下递归方程:
T(n) = 5T(n/5)+(5sin^5(5n^5)+5)*n
T(n) = T(n/4)+2sin^2(n^4)
我可以很容易地看到两个方程都符合主定理的第二种情况，
但由于 sin 是一个循环函数，似乎足够大的 N
可能使它真正接近于零。
所以，我们总能找到两个常数 c1,c2 的 N > N0(根据 theta 定义)
这将不赞成它..
真的可以用主定理解决吗？
谢谢
最佳答案
我认为你是对的，主定理在这里不适用。这样做的原因是 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) ，它不是多项式，所以主定理在这种情况下无效。
关于data-structures - 主定理 - 第二个案例问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/18661196/