如何解决一些硬核递归？

Question

我正试图为我的算法类解决这些递归问题。有人能帮我吗?因为大师定理不起作用，我不能计算第一棵树上发生的和，我也没有看到第二个很好的解决例子！

T(n) = 2*T(n/3) + n/log^2(n)

T(n) = T(n-10) + logn

Answer 1

第一个例子是关于主定理的工作：a=2, b=3, f=n/log^2(n)。log_b(a) < 1，所以这是第三种情况，因为f(n)在任何k中都比n^(log_b(a))*log^k(n)长得快。这意味着主要工作是在递归和T(n)=O(n/log^2(n))之外完成的。

第二个例子可以这样解决：

T(n)
= T(n - 10) + log(n)
= ...
= log(n) + log(n - 10) + ...
= log(n * (n-10) * (n-20) * ...)
= [n = 10k]
= log(10^k) + log(k!)
= k*log(10) + k*log(k) - k + O(log(k))
= O(k*log(k))
= O(n*log(n))