recursion - 获得递归方程的封闭形式并比较哪个更快

Question

如果可能的话，得到这些方程的封闭形式。然后，确定哪个比另一个更快。

f(n) = 0.25f(n/3)+ f(n/10) + logn, f(1) =  1

g(n) = n + log(n-1)^2 + 1

在这些方程式中，我是否必须扩展这些递归并尝试发现其中的模式？我真的不知道如何直观地计算封闭形式

标签： recursiontimecomplexity-theory

Answer 1

简短回答：g(n)>f(n) 详细回答： g 甚至不是递归的，因此您可以立即看到 g(n)=O(n)。f(n) <f(n/2)+logn 根据主定理，您可以近似为 Θ(logn)