以下递归方法的运行时分析 [英] runtime analysis of the following recursive method
问题描述
有人可以帮我进行以下代码的运行时分析吗:
Can someone please help me with the run-time analysis of the following code:
public static void f(int n)
{
for (int i = 0; i <= n; i++)
{
System.out.print("+" + i);
}
if (n <= 1)
{
return;
} else
{
f(n / 3);
f(n / 3);
}
}
根据我的说法,代码的递归公式的运行时为:
According to me, the run-time for the recursive formula for the code is:
T(n)= cn + 2T(n/3)
T(n) = cn + 2T(n/3)
我认为答案应该是Θ(nlog(n))
,但是从书本上的解答来看,答案是Θ(n)
.
本书还说为了简单起见,假设n = 3^k
.
And I think the answer should be Θ(nlog(n))
, but the book solutions show it to be Θ(n)
.
Also the book says to assume n = 3^k
for simplicity.
有人可以给我解释正确的答案吗?
Can someone please explain the correct answer to me?
推荐答案
考虑使用主定理.您的情况对应于情况1,其中f(n)= cn为O(n). 在a = 2和b = 3的情况下,应用定理,我们得出T(n)是bigTheta(n ^ log3(2)),也就是BigTheta(n).
Consider using the Master Theorem. Your situation corresponds to Case 1, where f(n)=cn is O(n). with a=2 and b=3, and applying the theorem, we have that T(n) is bigTheta(n^log3(2)), which is BigTheta(n).
希望对您有帮助...
Hope it helps ...
这篇关于以下递归方法的运行时分析的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!