以下递归方法的运行时分析 [英] 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屋！