给定以下递归方程：
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，这将不赞成它。
用主定理真的可以解决吗？
谢谢
问问题
299 次
1 回答
3
我认为你是对的，主定理不适用于这里。这样做的原因是 和 之间的差f(n)必须n^(log_b(a))是多项式的。（请参阅主定理递归：多项式差异究竟是什么？）
在您的情况下：
((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)，这不是多项式，因此主定理在这种情况下无效。
于 2013-09-13T17:30:36.817 回答