主定理 - 第二种情况问题

Question

给定以下递归方程：

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

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

但由于正弦是一个周期函数，因此足够大的 N 可能会使它非常接近零。 因此，我们总是能够找到一个 N > N0，对于两个常数 c1、c2（通过 Θ 定义） 将其驳回。

使用主定理真的能解决它吗？

谢谢

- Rouki

Answer 1

我认为你是正确的，主定理在这里不适用。原因是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)，它不是多项式，所以主定理在这种情况下无效。

- Lumlum